Universität Paderborn » SFB 901 » Events


Talk given by Michael Etscheid (Universität Bonn)

Begin: Wed, 04. of Nov 2015 ( 2:00 PM)
Location: Fürstenallee 11, room F1.110


We study the convergence time of local search for a standard machine scheduling problem in which jobs are assigned to identical or related machines. Local search corresponds to the best response dynamics that arises when jobs selfishly try to minimize their costs. We assume that each machine runs a coordination mechanism that determines the order of execution of jobs assigned to it. We obtain various new polynomial and pseudo-polynomial bounds for the well-studied coordination mechanisms Makespan and Shortest-Job-First, using worst-case and smoothed analysis. We also introduce a natural coordination mechanism FIFO, which takes into account the order in which jobs arrive at a machine, and study both its impact on the convergence time and its price of anarchy.

This is joint work with Tobias Brunsch and Heiko Röglin.