Estimating the makespan of the two-valued restricted assignment problem
type: Item
instance of: scholarly article
title: Estimating the makespan of the two-valued restricted assignment problem
zbMATH Open document ID: 1393.90057
author: Klaus Jansen
author: K. Land
author: Marten Maack
published in: Algorithmica
publication date: 2018-05-23T00:00:00Z
full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/6046/
review text: The paper deals with a scheduling problem of unrelated machines, where each considered job from a finite set of jobs must be assigned to one of the machines which are able to process the job. Each couple job-machine is connected to an individual processing time of the job on the machine. The sum of all processing times of the jobs assigned to a machine is denoted as the makespan of the machine. Objective of the restricted assignment problem is to minimize the maximal makespan across the set of machines. The authors focused their effort on a theoretical research concerning a special case of the above problem, where only two different values of processing time are taken into account. The goal of the research consists in improvement of the integrality gap estimation, what is ratio of optimal objective function values of the original integer programming problem and the linear programming relaxation of the problem. The authors were successful in improving the integrality gap from the previously known value of 11/6 to the value of 5/3. This excellent result was achieved by utilizing and improving the Svensson's bound and search technique. The presented research is properly described by a sequence of theorems and lemmas and carefully performed proofs. Generally, the paper constitutes a valuable piece of work for community of professionals in the theory of algorithms.
reviewed by: Jaroslav Janáček
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 90B80
zbMATH DE Number: 6872030
zbMATH Keywords: unrelated scheduling
zbMATH Keywords: restricted assignment
zbMATH Keywords: configuration LP
zbMATH Keywords: integrality gap
zbMATH Keywords: estimation algorithm
MaRDI profile type: Publication
OpenAlex ID: W2607924865
cites work: The Santa Claus problem
cites work: On (1,∊)-Restricted Assignment Makespan Minimization
cites work: Graph balancing: a special case of scheduling unrelated parallel machines
cites work: An approximation algorithm for the generalized assignment problem
cites work: The 2-valued case of makespan minimization with assignment constraints
cites work: Approximation algorithms for scheduling unrelated parallel machines
cites work: An optimal rounding gives a better approximation for scheduling unrelated machines
cites work: Santa Claus Schedules Jobs on Unrelated Machines
cites work: On the Configuration-LP for Scheduling on Unrelated Machines
DOI: 10.1007/S00453-017-0314-4
description: scientific article; zbMATH DE number 6872030