Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

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

Action:

login to update

Options:




Library Locked Library locked




Author, Editor(s)

Author(s):

Chen, Xujin
Epstein, Leah
Kleiman, Elena
van Stee, Rob

dblp
dblp
dblp
dblp

Not MPG Author(s):

Chen, Xujin
Epstein, Leah
Kleiman, Elena

BibTeX cite key*:

ChEpKS13

Title

Title*:

Maximizing the minimum load: The cost of selfishness

Journal

Journal Title*:

Theoretical Computer Science

Journal's URL:


Download URL
for the article:


Language:

English

Publisher

Publisher's
Name:

Elsevier

Publisher's URL:

http://www.journals.elsevier.com/theoretical-computer-science/

Publisher's
Address:


ISSN:

0304-3975

Vol, No, pp, Date

Volume*:

482

Number:


Publishing Date:

April 2013

Pages*:

9-19

Number of
VG Pages:

11

Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) Abstract:

We consider a scheduling problem where each job is controlled by a
selfish agent, who is only interested in minimizing its own cost,
defined as the total load of the machine that its job is assigned
to. We consider the objective of maximizing the minimum load (the
value of the cover) over the machines. Unlike the regular makespan
minimization problem, which was extensively studied in a game
theoretic context, this problem has not been considered in this
setting before.

We study the price of anarchy (\poa) and the price of stability
(\pos). These measures are unbounded already for two uniformly
related machines \cite{EpKS10}, and therefore we focus on
identical machines. We show that the $\pos$ is 1, and derive tight
bounds on the pure $\poa$ for $m\leq 7$ and on the overall pure
$\poa$, showing that its value is exactly 1.7. To achieve the
upper bound of 1.7, we make an unusual use of weighting functions.
Finally, we show that the mixed $\poa$ grows exponentially with
$m$ for this problem.

In addition, we consider a similar setting of selfish jobs with a
different objective of minimizing the maximum ratio between the
loads of any pair of machines in the schedule. We show that under
this objective the $\pos$ is 1 and the pure $\poa$ is 2, for any
$m\geq 2$.

URL for the Abstract:


Categories,
Keywords:


HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Internal

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:

@ARTICLE{ChEpKS13,
AUTHOR = {Chen, Xujin and Epstein, Leah and Kleiman, Elena and van Stee, Rob},
TITLE = {Maximizing the minimum load: The cost of selfishness},
JOURNAL = {Theoretical Computer Science},
PUBLISHER = {Elsevier},
YEAR = {2013},
VOLUME = {482},
PAGES = {9--19},
MONTH = {April},
ISBN = {0304-3975},
}


Entry last modified by Rob van Stee, 02/17/2014
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)
[Library]
Created
01/14/2014 03:54:39 PM
Revision
0.



Editor
Rob van Stee



Edit Date
14/01/2014 15:54:39