Estimating the makespan of the two-valued restricted assignment problem

DOI10.1007/s00453-017-0314-4zbMath1393.90057OpenAlexW2607924865MaRDI QIDQ1751100

Kati Land, Klaus Jansen, Marten Maack

Publication date: 23 May 2018

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/6046/

zbMATH Keywords

integrality gapestimation algorithmrestricted assignmentconfiguration LPunrelated scheduling

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Discrete location and assignment (90B80)

Related Items (2)

Makespan minimization on unrelated parallel machines with a few bags ⋮ Unnamed Item

Cites Work

• Approximation algorithms for scheduling unrelated parallel machines
• An approximation algorithm for the generalized assignment problem
• The 2-valued case of makespan minimization with assignment constraints
• Graph balancing: a special case of scheduling unrelated parallel machines
• An optimal rounding gives a better approximation for scheduling unrelated machines
• The Santa Claus problem
• On the Configuration-LP for Scheduling on Unrelated Machines
• Santa Claus Schedules Jobs on Unrelated Machines
• On (1,∊)-Restricted Assignment Makespan Minimization

This page was built for publication: Estimating the makespan of the two-valued restricted assignment problem