English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

Maximizing the Minimum Load for Selfish Agents

MPS-Authors
/persons/resource/persons45543

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

External Ressource
No external resources are shared
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available
Citation

Epstein, L., & van Stee, R. (2008). Maximizing the Minimum Load for Selfish Agents. In E. S. Laber, C. Bornstein, L. T. Noguiera, & L. Faria (Eds.), LATIN 2008: Theoretical Informatics (pp. 264-275). Berlin: Springer. doi:10.1007/978-3-540-78773-0_23.


Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-1C2B-F
Abstract
We consider the problem of maximizing the minimum load for machines that are controlled by selfish agents, who are only interested in maximizing their own profit. Unlike the classical load balancing problem, this problem has not been considered for selfish agents until now. For a constant number of machines, $m$, we show a monotone polynomial time approximation scheme (PTAS) with running time that is linear in the number of jobs. It uses a new technique for reducing the number of jobs while remaining close to the optimal solution. We also present an FPTAS for the classical machine covering problem, i.e., where no selfish agents are involved (the previous best result for this case was a PTAS) and use this to give a monotone FPTAS. Additionally, we give a monotone approximation algorithm with approximation ratio $\min(m,(2+\varepsilon)s_1/s_m)$ where $\varepsilon>0$ can be chosen arbitrarily small and $s_i$ is the (real) speed of machine $i$. Finally we give improved results for two machines.