English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  Max-min Online Allocations with a Reordering Puffer

Epstein, L., Levin, A., & van Stee, R. (2010). Max-min Online Allocations with a Reordering Puffer. In S. Abramsky, C. Gavoille, C. Kirchner, F. Meyer auf der Heide, & P. G. Spirakis (Eds.), Automata, Languages and Programming (pp. 336-347). Berlin: Springer. doi:10.1007/978-3-642-14165-2_29.

Item is

Files

show Files
hide Files
:
bcover-c.pdf (Any fulltext), 105KB
 
File Permalink:
-
Name:
bcover-c.pdf
Description:
-
OA-Status:
Visibility:
Private
MIME-Type / Checksum:
application/pdf
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Epstein, Leah1, Author
Levin, Asaf1, Author
van Stee, Rob2, Author           
Affiliations:
1External Organizations, ou_persistent22              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 Abstract: We consider a scheduling problem where each job is controlled by a selfish agent, who is only interested in minimizing its own cost, which is defined as the total load on the machine that its job is assigned to. We consider the objective of maximizing the minimum load (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). Since these measures are unbounded already for two uniformly related machines, we focus on identical machines. We show that the $\pos$ is 1, and we derive tight bounds on the $\poa$ for $m\leq6$ and nearly tight bounds for general $m$. In particular, we show that the $\poa$ is at least 1.691 for larger $m$ and at most 1.7. Hence, surprisingly, the $\poa$ is less than the $\poa$ for the makespan problem, which is 2. To achieve the upper bound of 1.7, we make an unusual use of weighting functions. Finally, in contrast we show that the mixed $\poa$ grows exponentially with $m$ for this problem, although it is only $\Theta(\log m/\log \log m)$ for the makespan. In addition we consider a similar setting with a different objective which is minimizing the maximum ratio between the loads of any pair of machines in the schedule. We show that under this objective for general $m$ the $\pos$ is 1, and the $\poa$ is 2.

Details

show
hide
Language(s): eng - English
 Dates: 20102010
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 536744
DOI: 10.1007/978-3-642-14165-2_29
URI: http://dx.doi.org/10.1007/978-3-642-14165-2_29
Other: Local-ID: C1256428004B93B8-2603A794E779C386C12577F4005161E8-EpLeSt10
 Degree: -

Event

show
hide
Title: 37th International Colloquium on Automata, Languages and Programming
Place of Event: Bordeaux, France
Start-/End Date: 2010-07-06 - 2010-07-10

Legal Case

show

Project information

show

Source 1

show
hide
Title: Automata, Languages and Programming
  Subtitle : 37th International Colloquium, ICALP 2010
  Abbreviation : ICALP 2010
Source Genre: Proceedings
 Creator(s):
Abramsky, Samson1, Editor
Gavoille, Cyril1, Editor
Kirchner, Claude1, Editor
Meyer auf der Heide, Friedhelm1, Editor
Spirakis, Paul G.2, Editor           
Affiliations:
1 External Organizations, ou_persistent22            
2 Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019            
Publ. Info: Berlin : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 336 - 347 Identifier: ISBN: 9-783642-14164-5

Source 2

show
hide
Title: Lecture Notes in Computer Science
  Abbreviation : LNCS
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 6198 Sequence Number: - Start / End Page: - Identifier: -