Sonderkolloquium, Dr. Chidambaram Amalai, ETH Zürich / am 10.04.2017

10.04.2017 von 15:00 bis 16:30

Ludewig-Meyn-Str. 2. Raum Ü2/K (LMS2, R. Ü2/K)

Titel: Algorithmic Advances in Allocation and Scheduling

Abstract: We study the restricted case of Scheduling on Unrelated Parallel
Machines. In this problem, we are given a set of jobs J with processing
times p_j and each job may be scheduled only on some subset of machines
S_j. The goal is to find an assignment of jobs to machines to minimize
the time by which all jobs can be processed. In a seminal paper,
Lenstra, Shmoys, and Tardos designed an elegant 2-approximation for the
problem in 1987. The question of whether approximation algorithms with
better guarantees exist for this classic scheduling problem has since
remained a source of mystery.

In recent years, with the improvement of our understanding of
Configuration LPs, it now appears an attainable goal to design such an
algorithm. Our main contribution is to make progress towards this goal.
When the processing times of jobs are either 1 or epsilon < 1, we design
an approximation algorithm whose guarantee tends to 1+sqrt(3)/2 =
1.8660254, for the interesting cases when epsilon approaches 0. This
improves on the 2 - epsilon_0 guarantee recently obtained by
Chakrabarty, Khanna, and Li for some constant epsilon_0 > 0.


Prof. Jansen

Diesen Termin meinem iCal-Kalender hinzufügen