> Details

Jansen, Klaus [Author]; Land, Kati [Author]; Maack, Marten [Author] ; Klaus Jansen and Kati Land and Marten Maack [Contributor]

Estimating The Makespan of The Two-Valued Restricted Assignment Problem

Reference
management

Bookmarks

Remove from
bookmarks

Share this on Whatsapp

Close

Bookmarks



You can manage bookmarks using lists, please log in to your user account for this.
  • Media type: Text; E-Article; Electronic Conference Proceeding
  • Title: Estimating The Makespan of The Two-Valued Restricted Assignment Problem
  • Contributor: Jansen, Klaus [Author]; Land, Kati [Author]; Maack, Marten [Author]
  • Published: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2016
  • Language: English
  • DOI: https://doi.org/10.4230/LIPIcs.SWAT.2016.24
  • Keywords: estimation algorithm ; unrelated scheduling ; configuration LP ; integrality gap ; restricted assignment
  • Origination:
  • Footnote: Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
  • Description: 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.
  • Access State: Open Access