BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Estimating The Makespan of The Two-Valued Restricted Assignment Problem Land, Kati


We consider a special case of the scheduling problem on unrelated machines, namely the Restricted Assignment Problem with two diifferent processing times. We show that the configuration LP has an integrality gap of at most 5=3 1:667 for this problem. This allows us to estimate the optimal makespan within a factor of 5/3 , improving upon the previously best known estimation algorithm with ratio 11=6 1:833 due to Chakrabarty, Khanna, and Li. This is joint work with Klaus Jansen and Marten Maack.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International