On the Configuration-LP of the Restricted Assignment Problem

DOI10.1137/1.9781611974782.176zbMath1415.90041arXiv1611.01934OpenAlexW2949207626MaRDI QIDQ4575925

Lars Rohwedder, Klaus Jansen

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

linear programmingschedulinglocal searchintegrality gapestimation algorithms

Mathematics Subject Classification ID

Linear programming (90C05) Deterministic scheduling theory in operations research (90B35) Discrete location and assignment (90B80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (12)

Makespan minimization on unrelated parallel machines with a few bags ⋮ Approximation algorithms for the graph balancing problem with two speeds and two job lengths ⋮ Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations ⋮ A note on the integrality gap of the configuration LP for restricted Santa Claus ⋮ Structural parameters for scheduling with assignment restrictions ⋮ Structured Instances of Restricted Assignment with Two Processing Times ⋮ Compact LP Relaxations for Allocation Problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Simpler and Better Algorithms for Minimum-Norm Load Balancing ⋮ Lazy Local Search Meets Machine Scheduling

This page was built for publication: On the Configuration-LP of the Restricted Assignment Problem