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 Citations and Data
Attribution-NonCommercial-NoDerivatives 4.0 International