License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2016.24
URN: urn:nbn:de:0030-drops-60467
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6046/
Jansen, Klaus ;
Land, Kati ;
Maack, Marten
Estimating The Makespan of The Two-Valued Restricted Assignment Problem
Abstract
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.
BibTeX - Entry
@InProceedings{jansen_et_al:LIPIcs:2016:6046,
author = {Klaus Jansen and Kati Land and Marten Maack},
title = {{Estimating The Makespan of The Two-Valued Restricted Assignment Problem}},
booktitle = {15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
pages = {24:1--24:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-011-8},
ISSN = {1868-8969},
year = {2016},
volume = {53},
editor = {Rasmus Pagh},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6046},
URN = {urn:nbn:de:0030-drops-60467},
doi = {10.4230/LIPIcs.SWAT.2016.24},
annote = {Keywords: unrelated scheduling, restricted assignment, configuration LP, integrality gap, estimation algorithm}
}
|
Keywords: |
|
unrelated scheduling, restricted assignment, configuration LP, integrality gap, estimation algorithm |
|
Collection: |
|
15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016) |
|
Issue Date: |
|
2016 |
|
Date of publication: |
|
22.06.2016 |
