Estimating The Makespan of The Two-Valued Restricted Assignment Problem

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~$\frac{5}{3} + \frac{1}{156} \approx 1.6731$ for this problem. This allows us to estimate the optimal makespan within a factor of~$\frac{5}{3} + \frac{1}{156}$,improving upon the previously best known estimation algorithm with ratio~$\frac{11}{6} \approx \numprint{1.833}$ due to Chakrabarty, Khanna, and Li \cite{CKL15}.

Vorschau

Logo BII

BII

Rechte

Nutzung und Vervielfältigung:

Keine Lizenz. Es gelten die Bestimmungen des deutschen Urheberrechts (UrhG).

Bitte beachten Sie, dass einzelne Bestandteile der Publikation anderweitigen Lizenz- bzw. urheberrechtlichen Bedingungen unterliegen können.

Zitieren

Zitierform:
Zitierform konnte nicht geladen werden.