License
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://drops.dagstuhl.de/opus/volltexte/2016/6046/
Go to the corresponding LIPIcs Volume Portal


Jansen, Klaus ; Land, Kati ; Maack, Marten

Estimating The Makespan of The Two-Valued Restricted Assignment Problem

pdf-format:
LIPIcs-SWAT-2016-24.pdf (0.6 MB)


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
Seminar: 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
Issue Date: 2016
Date of publication: 21.06.2016


DROPS-Home | Fulltext Search | Imprint Published by LZI