Estimating the Makespan of the Two-Valued Restricted Assignment Problem.

Jansen, Klaus, Land, Kati and Maack, Marten (2017) Estimating the Makespan of the Two-Valued Restricted Assignment Problem. Algorithmica, 80 . DOI 10.1007/s00453-017-0314-4.

Full text not available from this repository.

Supplementary data:

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 \frac{5}{3} \approx 1.667 for this problem. This allows us to estimate the optimal makespan within a factor of \frac{5}{3}, improving upon the previously best known estimation algorithm with ratio \frac{11}{6} \approx 1.833 due to Chakrabarty et al. (in: Proceedings of the twenty-sixth annual ACM-SIAM symposium on discrete algorithms (SODA 2015), pp 1087–1101, 2015).

Document Type: Article
Keywords: Unrelated scheduling, Restricted assignment, Configuration LP, Integrality gap, Estimation algorithm
Research affiliation: Kiel University > Kiel Marine Science
OceanRep > The Future Ocean - Cluster of Excellence
Kiel University
Refereed: Yes
Open Access Journal?: No
DOI etc.: 10.1007/s00453-017-0314-4
ISSN: 0178-4617
Projects: Future Ocean
Date Deposited: 19 Dec 2017 10:22
Last Modified: 29 Apr 2019 14:55
URI: http://oceanrep.geomar.de/id/eprint/40869

Actions (login required)

View Item View Item