Invited Session Wed.1.H 3010

Wednesday, 10:30 - 12:00 h, Room: H 3010

Cluster 1: Approximation & online algorithms [...]

Scheduling and packing: Approximation with algorithmic game theory in mind


Chair: Asaf Levin



Wednesday, 10:30 - 10:55 h, Room: H 3010, Talk 1

Leah Epstein
Generalized selfish bin packing

Coauthor: Gyorgy Dosa


In bin packing games, an item has a positive weight and each item has a cost for every valid packing of the items. We study a class of such games where the cost of an item is the ratio between its weight and the total weight of items packed with it, i.e., cost sharing is based linearly on the weights of items. We study several types of pure Nash equilibria (NE): standard NE, strong NE, and strictly/weakly Pareto optimal NE. We show that any game of this class admits all these types of equilibria. We study the (asymptotic) prices of anarchy and stability (PoA and PoS) of the problem for these types of equilibria and general/unit weights. While the
case of general weights is strongly related to First Fit, and all the PoA values are 1.7, for unit weights they are all below 1.7. The strong PoA is equal to approximately 1.691 (another well-known number in bin packing) while the strictly Pareto optimal PoA is lower. The PoS values are 1, except for those of strong equilibria, which is 1.7 for general weights, and approximately 1.611824 for unit weights.



Wednesday, 11:00 - 11:25 h, Room: H 3010, Talk 2

Asaf Levin
A unified approach to truthful scheduling on related machines

Coauthors: Leah Epstein, Rob van Stee


We present a unified framework for designing deterministic monotone PTAS's for a wide class of scheduling problems on uniformly related machines. This class includes (among others) minimizing the makespan, maximizing the minimum load, and minimizing the lp norm of the machine loads vector. Previously, this kind of result was only known for the makespan objective. Monotone PTAS's have the property that an increase in the speed of a machine cannot decrease the amount of work assigned to it, and have an important role in mechanism design.
The key idea of our novel method is to show that it is possible to compute in polynomial time a structured nearly optimal schedule. An interesting aspect of our approach is that, in contrast to all known PTAS's, we avoid rounding any job sizes or speeds throughout. We can therefore find the exact best structured schedule using a dynamic programming. The state space encodes sufficient information such that no postprocessing is needed, allowing an elegant and relatively simple analysis. The monotonicity is a consequence of the fact that we find the best schedule in a specific collection of schedules.



Wednesday, 11:30 - 11:55 h, Room: H 3010, Talk 3

Rob van Stee
The price of anarchy for selfish ring routing is two

Coauthors: Xujin Chen, Benjamin Doerr, Xiaodong Hu, Weidong Ma, Carola Winzen


We analyze the network congestion game with atomic players, asymmetric strategies, and the maximum latency among all players as social cost. While this is an important social cost function, it has so far received relatively little attention in the literature.
We show that the price of anarchy is at most two, when the network is a ring and the link latencies are linear. This bound is tight. This is the first sharp bound for the maximum latency objective on a natural and important network topology.


  The best way to go for you to know the credible Michigan Payday Loans providers. In rare cases, the smarting in eyes and the tumefaction of eyelids can happen. In case of long term Cialis Black administration the side effects become less perceptible or disappear at all.