Maximizing the Minimum Load for Selfisch Agents

Authors Leah Epstein, Rob van Stee



PDF
Thumbnail PDF

File

DagSemProc.07261.10.pdf
  • Filesize: 351 kB
  • 19 pages

Document Identifiers

Author Details

Leah Epstein
Rob van Stee

Cite AsGet BibTex

Leah Epstein and Rob van Stee. Maximizing the Minimum Load for Selfisch Agents. In Fair Division. Dagstuhl Seminar Proceedings, Volume 7261, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
https://doi.org/10.4230/DagSemProc.07261.10

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.
Keywords
  • Scheduling
  • algorithmic mechanism design
  • maximizing minimum load

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail