**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**

**Abstract:**

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"** [...]