A quasi-polynomial approximation for the restricted assignment problem

DOI10.1007/978-3-319-59250-3_25zbMath1418.90232arXiv1701.07208OpenAlexW2585975065MaRDI QIDQ2401169

Klaus Jansen, Lars Rohwedder

Publication date: 31 August 2017

Full work available at URL: https://arxiv.org/abs/1701.07208

zbMATH Keywords

schedulingapproximationlocal searchunrelated machines

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Discrete location and assignment (90B80)

Related Items (10)

On the extension complexity of scheduling polytopes ⋮ Makespan minimization on unrelated parallel machines with a few bags ⋮ Approximation algorithms for the graph balancing problem with two speeds and two job lengths ⋮ A note on the integrality gap of the configuration LP for restricted Santa Claus ⋮ Structural parameters for scheduling with assignment restrictions ⋮ Restricted assignment scheduling with resource constraints ⋮ Compact LP Relaxations for Allocation Problems ⋮ Unnamed Item ⋮ Lazy Local Search Meets Machine Scheduling ⋮ On minimizing the makespan when some jobs cannot be assigned on the same machine

This page was built for publication: A quasi-polynomial approximation for the restricted assignment problem