de.mpg.escidoc.pubman.appbase.FacesBean
English

# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### Max-min Online Allocations with a Reordering Puffer

##### MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons45543

van Stee,  Rob
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

##### Locator
There are no locators available
##### Fulltext (public)
There are no public fulltexts available
##### Supplementary Material (public)
There is no public supplementary material available
##### Citation

Epstein, L., Levin, A., & van Stee, R. (2010). Max-min Online Allocations with a Reordering Puffer. In S. Abramsky, C. Gavoille, C. Kirchner, F. Meyer auf der Heide, & P. G. Spirakis (Eds.), Automata, Languages and Programming (pp. 336-347). Berlin: Springer. doi:10.1007/978-3-642-14165-2_29.

Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-1679-D
##### Abstract
We consider a scheduling problem where each job is controlled by a selfish agent, who is only interested in minimizing its own cost, which is defined as the total load on the machine that its job is assigned to. We consider the objective of maximizing the minimum load (cover) over the machines. Unlike the regular makespan minimization problem, which was extensively studied in a game theoretic context, this problem has not been considered in this setting before. We study the price of anarchy (\poa) and the price of stability (\pos). Since these measures are unbounded already for two uniformly related machines, we focus on identical machines. We show that the $\pos$ is 1, and we derive tight bounds on the $\poa$ for $m\leq6$ and nearly tight bounds for general $m$. In particular, we show that the $\poa$ is at least 1.691 for larger $m$ and at most 1.7. Hence, surprisingly, the $\poa$ is less than the $\poa$ for the makespan problem, which is 2. To achieve the upper bound of 1.7, we make an unusual use of weighting functions. Finally, in contrast we show that the mixed $\poa$ grows exponentially with $m$ for this problem, although it is only $\Theta(\log m/\log \log m)$ for the makespan. In addition we consider a similar setting with a different objective which is minimizing the maximum ratio between the loads of any pair of machines in the schedule. We show that under this objective for general $m$ the $\pos$ is 1, and the $\poa$ is 2.