Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor

Author(s):

Epstein, Leah
van Stee, Rob

dblp
dblp

Not MPG Author(s):

Epstein, Leah

Editor(s):

Laber, Eduardo Sany
Bornstein, Claudson
Noguiera, Loana Tito
Faria, Luerbio

dblp
dblp
dblp
dblp

Not MPII Editor(s):

Laber, Eduardo Sany
Bornstein, Claudson
Noguiera, Loana Tito
Faria, Luerbio

BibTeX cite key*:

vanStee2008a

Title, Booktitle

Title*:

Maximizing the minimum load for selfish agents


cover16.dvi (108.21 KB)

Booktitle*:

LATIN 2008: Theoretical Informatics, 8th Latin American Symposium

Event, URLs

URL of the conference:

http://www.latin08.org/

URL for downloading the paper:

http://www.springerlink.com/content/m4041512q2616208/fulltext.pdf

Event Address*:

Búzios, Brazil

Language:

English

Event Date*
(no longer used):


Organization:


Event Start Date:

7 April 2008

Event End Date:

11 April 2008

Publisher

Name*:

Springer

URL:

http://www.springer-ny.com/

Address*:

Berlin

Type:


Vol, No, Year, pp.

Series:

Lecture Notes in Computer Science

Volume:

4957

Number:


Month:

April

Pages:

264-275

Year*:

2008

VG Wort Pages:

12

ISBN/ISSN:

0302-9743

Sequence Number:


DOI:

10.1007/978-3-540-78773-0_23



Note, Abstract, ©


(LaTeX) 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.

Keywords:

algorithmic game theory, scheduling, max-min fairness



Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

experts only

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{vanStee2008a,
AUTHOR = {Epstein, Leah and van Stee, Rob},
EDITOR = {Laber, Eduardo Sany and Bornstein, Claudson and Noguiera, Loana Tito and Faria, Luerbio},
TITLE = {Maximizing the minimum load for selfish agents},
BOOKTITLE = {LATIN 2008: Theoretical Informatics, 8th Latin American Symposium},
PUBLISHER = {Springer},
YEAR = {2008},
VOLUME = {4957},
PAGES = {264--275},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {B{\'u}zios, Brazil},
MONTH = {April},
ISBN = {0302-9743},
DOI = {10.1007/978-3-540-78773-0_23},
}


Entry last modified by Rob van Stee, 12/10/2010
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Rob van Stee
Created
01/12/2009 12:48:03 PM
Revisions
4.
3.
2.
1.
0.
Editor(s)
Rob van Stee
Uwe Brahm
Rob van Stee
Rob van Stee
Rob van Stee
Edit Dates
12-10-2010 15:35:08
03/20/2009 02:55:47 PM
03/20/2009 09:57:51 AM
01/12/2009 01:45:42 PM
01/12/2009 12:48:03 PM
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
cover16.dvi