Selfish, local and online scheduling via vector fitting

We provide a dual fitting technique on a semidefinite program yielding simple proofs of tightbounds for the robust price of anarchy of several congestion and scheduling games under the sum of weighted completion times objective. The same approach also allows to bound the approximation ratio of local search algorithms and the competitive ratio of online algorithms for the scheduling problem $R‖\sum w_jC_j$. All of our results are obtained through a simple unified dual fitting argument on the same semidefinite programming relaxation, which can essentially be obtained through the first round of the Lasserre/Sum of Squares hierarchy. As our main application, we show that the known coordination ratio bounds of respectively $4, (3 + √5)/2 ≈2.618$, and $32/15 ≈ 2.133$ for the scheduling game $R‖\sum w_jC_j$ under the coordination mechanisms Smith’s Rule, Proportional Sharing and Rand (STOC 2011) can be extended to congestion games and obtained through this approach. For the natural restriction where the weight of each player is proportional to its processing time on every resource, we show that the last bound can be improved from $2.133$ to $2$. This improvement can also be made for general instances when considering the price of anarchy of the game, rather than the coordination ratio. As a further application of this technique in a game theoretic setting, we show that it recovers the tight bound of $(3 + √5)/2$ for the price of anarchy of weighted affine congestion games and the Kawaguchi-Kyan bound of $(1 + √2)/2$ for the pure price of anarchy of $P‖\sum w_jC_j$. Moreover, we show that this approach recovers the known tight approximation ratio of $(3 + √5)/2$ for a natural local search algorithm for $R‖\sum w_jC_j$, as well as the best currently known combinatorial approximation algorithm for this problem achieving an approximation ratio of $(5 + √5)/4 + ε ≈ 1.809 + ε$, and provide an almost matching lower bound. Finally, we show that this technique also extends to online algorithms by analyzing a randomized algorithm for $R‖\sum w_jC_j$ achieving a competitive ratio of $4$ in an online setting where the arrival order of the jobs is adversarial and the ordering on each machine is optimal.

• View at Publisher

Full Text ( Final Version , 729kb )