License
When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-12427
URL: http://drops.dagstuhl.de/opus/volltexte/2007/1242/
Go to the corresponding Portal


Epstein, Leah ; van Stee, Rob

Maximizing the Minimum Load for Selfisch Agents

pdf-format:
Document 1.pdf (352 KB)


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+eps)s_1/s_m)$ where $eps>0$ can be chosen arbitrarily small and $s_i$ is the (real) speed of machine $i$. Finally we give improved results for two machines.

BibTeX - Entry

@InProceedings{epstein_et_al:DSP:2007:1242,
  author =	{Leah Epstein and Rob van Stee},
  title =	{Maximizing the Minimum Load for Selfisch Agents},
  booktitle =	{Fair Division},
  year =	{2007},
  editor =	{Steven Brams and Kirk Pruhs and Gerhard Woeginger},
  number =	{07261},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2007/1242},
  annote =	{Keywords: Scheduling, algorithmic mechanism design, maximizing minimum load}
}

Keywords: Scheduling, algorithmic mechanism design, maximizing minimum load
Seminar: 07261 - Fair Division
Issue Date: 2007
Date of publication: 26.11.2007


DROPS-Home | Fulltext Search | Imprint Published by LZI