Monday, 16:15 - 16:40 h, Room: H 3004


Neil Olver
Approximation algorithms for scheduling via coordination mechanisms

Coauthors: Richard Cole, Jose R. Correa, Vasilis Gkatzelis, Vahab Mirrokni


We investigate the problem of scheduling on multiple unrelated machines, where the goal is to minimize the weighted sum of completion times. We primarily consider the game-theoretic version of the problem, where each job is an agent aiming to minimize its own completion time. However, as one outcome of our work we obtain the first combinatorial constant factor approximation algorithm for the NP-hard optimization problem.
We consider a number of different policies; rules specifying the scheduling on a machine for a given assignment. The most obvious choice is Smith's rule; for a given assignment of jobs to machines, this yields the optimal schedule. However, we show that other policies that give a suboptimal scheduling actually have much better equilibrium schedules, due to better incentives. By finding an approximate Nash equilibrium for one such policy via local search, we obtain a factor 2+ε approximation algorithm.
These results are obtained by the application of a common technique: a mapping of the strategy vectors into a carefully chosen inner product space. Once this structure is in place, the proofs are relatively short and elegant.


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


  . One of the main advantages of Sovaldi is that it can be used by patients belonging to all 4 genotypes. Buy Sovaldi is a very strong drug, and as all of them, it has a number of side effects that can be caused.