Journal Article @Article Artikel in Fachzeitschrift
 Show entries of: this year (2022) | last year (2021) | two years ago (2020) | Notes URL
 Action: login to update Options: Library locked Goto entry point

 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: (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
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