2006, English, Article edition: The price of approximate stability for scheduling tasks on two links Angel, Eric; Bampis, Evripidis; Pascual, Fanny

User activity

Share to:
 
Bookmark: http://trove.nla.gov.au/version/209572
Physical Description
  • text
Published
  • HAL - CCSD
  • 2006
Language
  • English

Edition details

Title
  • The price of approximate stability for scheduling tasks on two links
Author
  • Angel, Eric
  • Bampis, Evripidis
  • Pascual, Fanny
Published
  • HAL - CCSD
  • 2006
Physical Description
  • text
Subjects
Notes
  • We consider a \em scheduling game, where a set of selfish agents (traffic loads) want to be routed in exactly one of the two parallel links of a system. Every agent aims to minimize \em her own completion time, while the social objective is the \em makespan, i.e. the time at which the last agent finishes her execution. We study the problem of optimizing the makespan under the constraint that the obtained schedule is a (pure) Nash equilibrium, i.e. a schedule in which no agent has incentive to unilaterally change her strategy (link). We consider a relaxation of the notion of \em equilibrium by considering $\alpha$-approximate Nash equilibria, in which agents do not have \em sufficient incentive to unilaterally change their strategies: in an $\alpha$-approximate Nash equilibrium, no agent can decrease its cost by more than $\alpha$ multiplicative factor. Our main contribution is the study of the \em tradeoff between the \em approximation ratio for the makespan and the stability of the schedule (the value of $\alpha$). We first give an algorithm which provides a solution with an approximation ratio of $\frac87$ for the makespan and which is a 3-approximate Nash equilibrium, provided that the local policy of each link is \em Longest Processing Time (LPT). Furthermore, we show that a slight modification of the classical \em Polynomial Time Approximation Scheme (PTAS) of Graham allows to obtain a schedule whose makespan is arbitrarily close to the optimum while keeping a constant value for $\alpha$. Finally, we give bounds establishing relations between the value of $\alpha$ and the best possible value of the approximation ratio, provided that the local policies of the links are LPT. We also briefly examine the case where the local policies are SPT.
  • HAL:hal-00341356, version 1
  • HAL:http:/​/​hal.archives-ouvertes.fr/​hal-00341356/​en/​
  • DOI:10.1007/​11823285
Language
  • English
Contributed by
OAIster

Get this edition

  • Set up My libraries

    How do I set up "My libraries"?

    In order to set up a list of libraries that you have access to, you must first login or sign up. Then set up a personal list of libraries from your profile page by clicking on your user name at the top right of any screen.

  • All (1)
  • Unknown (1)
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.

User activity


e.g. test cricket, Perth (WA), "Parkes, Henry"

Separate different tags with a comma. To include a comma in your tag, surround the tag with double quotes.

Be the first to add a tag for this edition

Be the first to add this to a list

Comments and reviews

What are comments? Add a comment

No user comments or reviews for this version

Add a comment