Abstract We study fair allocations of indivisible goods and chores in conjunction with system efficiency, measured by two social welfare functions, namely utilitarian and egalitarian welfare. To model preference, each agent is associated with a cardinal and additive valuation function. The fairness criteria we are concerned with are equitability up to any item (EQX) and equitability up to one item (EQ1). For the trade-off between fairness and efficiency, we investigate efficiency loss under these fairness constraints and establish the price of fairness. From the computational perspective, we provide a complete picture of the computational complexity of (i) deciding the existence of an EQX/EQ1 and welfare-maximizing allocation; (ii) computing a welfare maximizer among all EQX/EQ1 allocations.

Abstract We study several fairness notions in allocating indivisible chores (i.e., items with disutilities) to agents who have additive and submodular cost functions. The fairness criteria we are concerned with are envy-free up to any item, envy-free up to one item, maximin share (MMS), and pairwise maximin share (PMMS), which are proposed as relaxations of envy-freeness in the setting of additive cost functions. For allocations under each fairness criterion, we establish their approximation guarantee for other fairness criteria. Under the additive setting, our results show strong connections between these fairness criteria and, at the same time, reveal intrinsic differences between goods allocation and chores allocation. However, such strong relationships cannot be inherited by the submodular setting, under which PMMS and MMS are no longer relaxations of envy-freeness and, even worse, few non-trivial guarantees exist. We also investigate efficiency loss under these fairness constraints and establish their prices of fairness.

Selfish routing is one of the fundamental models in the study of network traffic systems. While most literature assumes essentially static flows, game theoretical models of dynamic flows began to draw attention recently [1, 5].

Abstract This article is concerned with the design of fault‐tolerant access networks for cost‐effective communications—deploying network links and service providers (SPs) at a minimum cost, while ensuring error tolerance ability via the ring architecture. Given a set of service subscribers (SSs) in an access network, we are required to determine the locations and capacities of service providers, and to establish network links in terms of rings connecting SSs to SPs. We pay link costs for ring constructions and pay management costs for selecting SPs with capacities sufficient to manage the SSs in their rings. The network design aims to minimize the sum of the link costs and the management costs. Two APX‐hard problems in the general network design are studied in this article to address the scalable and modular features of SP capacities. Despite the logarithmic inapproximability that we show for one problem, constant‐factor approximation algorithms are proposed to solve the other problem and its variant in quartic time. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009

Previous article A Note on "An On-Line Scheduling Heuristic with Better Worst Case Ratio than Graham's List Scheduling"R. Chandrasekaran, Bo Chen, Gábor Galambos, P. R. Narayanan, André Van Vliet, and Gerhard J. WoegingerR. Chandrasekaran, Bo Chen, Gábor Galambos, P. R. Narayanan, André Van Vliet, and Gerhard J. Woegingerhttps://doi.org/10.1137/S0097539793258775PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAbout[1] Google Scholar[2] Gábor Galambos and , Gerhard Woeginger, An on‐line scheduling heuristic with better worst‐case ratio than Graham’s list scheduling, SIAM J. Comput., 22 (1993), 349–355 94b:90031 LinkISIGoogle Scholar[3] Google ScholarKeywordscombinatorial problemsschedulingworst-case boundson-line algorithms Previous article FiguresRelatedReferencesCited ByDetails A survey on makespan minimization in semi-online environmentsJournal of Scheduling, Vol. 21, No. 3 | 13 April 2018 Cross Ref Scheduling Web Advertisements: A Note on the Minspace ProblemJournal of Scheduling, Vol. 8, No. 1 | 1 Jan 2005 Cross Ref On-line scheduling revisitedJournal of Scheduling, Vol. 3, No. 6 | 1 January 2000 Cross Ref Online Scheduling RevisitedAlgorithms - ESA 2000 | 11 February 2003 Cross Ref A Review of Machine Scheduling: Complexity, Algorithms and ApproximabilityHandbook of Combinatorial Optimization | 1 Jan 1998 Cross Ref Volume 26, Issue 3| 1997SIAM Journal on Computing605-872 History Published online:28 July 2006 InformationCopyright © 1997 Society for Industrial and Applied MathematicsKeywordscombinatorial problemsschedulingworst-case boundson-line algorithmsMSC codes90B3590C27PDF Download Article & Publication DataArticle DOI:10.1137/S0097539793258775Article page range:pp. 870-872ISSN (print):0097-5397ISSN (online):1095-7111Publisher:Society for Industrial and Applied Mathematics

This paper shows that a greedy algorithm for three machine open shop scheduling with the objective to minimize the makespan provides schedules with the worst-case performance ratio 5/3. A linear time heuristic is presented which improves the schedules and reduces the ratio to 3/2. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

This paper addresses the problem of scheduling N jobs on M identical parallel machines with the objective of minimizing the makespan. Jobs are divided into B batches. A sequence-independent batch setup time on a machine is incurred whenever the machine starts its processing on or switches it from a job in one batch to a job in another batch. On the basis of a heuristic for this NP-hard problem proposed by Monma and Potts, a modified heuristic that requires the same implementing time $O(N + (M + B)\log (M + B))$ and is asymptotically optimal is presented. Furthermore, for a certain class of problems, which includes the case in which each batch contains a single job, it has the worst-case performance ratio $\tau _M = \max \{ {\frac{{3M}}{{2M + 1}},\frac{{3M - 4}}{{2M - 2}}} \}$.