Monday, 13:45 - 14:10 h, Room: H 3021


Andreas Wiese
A new approach to online scheduling: Approximating the optimal competitive ratio

Coauthors: Elisabeth G√ľnther, Olaf Maurer, Nicole Megow


We propose a new approach to competitive analysis in online scheduling by introducing the concept of online approximation schemes. Such a scheme algorithmically constructs an online algorithm with a competitive ratio arbitrarily close to the best possible competitive ratio for any online algorithm. Also, it provides algorithmic means to compute the actual value of the best possible competitive ratio up to an arbitrary accuracy.
We study the problem of scheduling jobs online to minimize the weighted sum of completion times on parallel, related, and unrelated machines. By constructing online approximation schemes we derive both deterministic and randomized algorithms which are almost best possible among all online algorithms of the respective settings. We also generalize our techniques to arbitrary monomial cost functions and apply them to the makespan objective. Our method relies on an abstract characterization of online algorithms combined with various simplifications and transformations.


Talk 2 of the invited session Mon.2.H 3021
"Scheduling algorithms II" [...]
Cluster 2
"Combinatorial optimization" [...]


  cash advance online . Of course, the choice is not that easy, as there exist great number of different preparations. Notwithstanding, Buy Cialis Online is the one that definitely differs from all other products.