Please use this identifier to cite or link to this item:
Title: The cost of selfishness for maximizing the minimum load on uniformly related machines
Authors: Epstein, L.
Kleiman, E.
Van Stee, Rob
First Published: 6-Oct-2012
Publisher: Springer US
Citation: Journal of Combinatorial Optimization, 2014, 27 (4), pp. 767-777
Abstract: Consider the following scheduling game. A set of jobs, each controlled by a selfish agent, are to be assigned to m uniformly related machines. The cost of a job is defined as the total load of the machine that its job is assigned to. A job is interested in minimizing its cost, while the social objective is maximizing the minimum load (the value of the cover) over the machines. This goal is different from the regular makespan minimization goal, which was extensively studied in a game theoretic context. We study the price of anarchy (poa) and the price of stability (pos) for uniformly related machines. The results are expressed in terms of s, which is the maximum speed ratio between any two machines. For uniformly related machines, we prove that the pos is unbounded for s>2, and the poa is unbounded for s≥2. For the remaining cases we show that while the poa grows to infinity as s tends to 2, the pos is at most 2 for any s≤2. © 2012 Springer Science+Business Media New York.
DOI Link: 10.1007/s10878-012-9555-y
ISSN: 1382-6905
eISSN: 1573-2886
Version: Post-print
Status: Peer-reviewed
Type: Journal Article
Rights: Copyright © Springer Science+Business Media New York 2012. The file associated with this record is distributed under the Creative Commons “Attribution Non-Commercial No Derivatives” licence, further details of which can be found via the following link:
Appears in Collections:Published Articles, Dept. of Computer Science

Files in This Item:
File Description SizeFormat 
mc_journal_B_joco_sec_revision.pdfPost-review (final submitted)494.57 kBUnknownView/Open

Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.