Estimating the makespan of the two-valued restricted assignment problem

DOI10.1007/S00453-017-0314-4MaRDI QIDQ1751100zbMATH OpenOpenAlexFDO

Authors Klaus Jansen, K. Land, 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

estimation algorithmintegrality gaprestricted assignmentconfiguration LPunrelated scheduling

Mathematics Subject Classification ID

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

Recommendations

• Estimating the makespan of the two-valued restricted assignment problem
• On the configuration-LP of the restricted assignment problem
• On \((1,\varepsilon)\)-restricted assignment makespan minimization
• A quasi-polynomial approximation for the restricted assignment problem

Cites work

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

Cited in

(5)

• Graph balancing with orientation costs
• Makespan minimization on unrelated parallel machines with a few bags
• The 2-valued case of makespan minimization with assignment constraints
• Better trees for Santa Claus
• Estimating the makespan of the two-valued restricted assignment problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1751100)