2026-07-23T21:02:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6046 2024-03-06T10:37:31Z ddc:004 open_access

Estimating The Makespan of The Two-Valued Restricted Assignment Problem Jansen, Klaus Land, Kati Maack, Marten unrelated scheduling restricted assignment configuration LP integrality gap estimation algorithm We consider a special case of the scheduling problem on unrelated machines, namely the Restricted Assignment Problem with two different 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Klaus Jansen and Kati Land and Marten Maack 2016 Is Part Of LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2016.24 urn:nbn:de:0030-drops-60467 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.24 eng https://creativecommons.org/licenses/by/3.0/legalcode