Monday, 15:45 - 16:10 h, Room: H 3004


Ruben Hoeksma
Price of anarchy for minsum related machine scheduling

Coauthor: Marc Uetz


We consider related machine scheduling to minimize the total completion time ∑ Cj. This problem is well known to be solved in polynomial time by a classical algorithm of Horowitz and Sahni. Instead of the centralized optimal solution, however, we are interested in the situation where each job individually chooses the machine on which it is processed. We analyze the quality of the resulting Nash equilibria in relation to the objective value in the optimal solution, also known as the price of anarchy. Complementing recent results by Cole et al. on the unrelated machine problem where the price of anarchy equals exactly 4, we show that the local SPT rule results in a price of anarchy between e/(e-1) and 2. To obtain the upper bound of 2, we use a smoothness argument in the flavor of recent work of Roughgarden, blended with a new characterization of the structure of optimal solutions.


Talk 2 of the invited session Mon.3.H 3004
"Interactions between optimization and game theory in scheduling" [...]
Cluster 2
"Combinatorial optimization" [...]


  There are three major facts that should be watched out for in all payday loans in the United States. When the problem is not treated, it can ruin intimate life of couples and destroy their relationships. Viagra Professional was produces not to let this happen. Professional means highly qualified. It strikes the target and doesn't allow a disorder to occupy man's body.