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 = {18624405},
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 