University of Leicester
Browse

The cost of selfishness for maximizing the minimum load on uniformly related machines

Download (494.57 kB)
journal contribution
posted on 2016-04-20, 09:17 authored by L. Epstein, E. Kleiman, Rob Van Stee
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.

History

Citation

Journal of Combinatorial Optimization, 2014, 27 (4), pp. 767-777

Author affiliation

/Organisation/COLLEGE OF SCIENCE AND ENGINEERING/Department of Computer Science

Version

  • AM (Accepted Manuscript)

Published in

Journal of Combinatorial Optimization

Publisher

Springer US

issn

1382-6905

eissn

1573-2886

Copyright date

2012

Available date

2016-04-20

Publisher version

http://link.springer.com/article/10.1007/s10878-012-9555-y

Language

en

Usage metrics

    University of Leicester Publications

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC