Compact LP Relaxations for Allocation Problems

DOI10.4230/OASIcs.SOSA.2018.11zbMath1436.90050OpenAlexW2783842799MaRDI QIDQ5240426

Lars Rohwedder, Klaus Jansen

Publication date: 25 October 2019

Full work available at URL: https://doi.org/10.4230/OASIcs.SOSA.2018.11

zbMATH Keywords

linear programmingmakespanunrelated machinesmax-minrestricted assignmentSanta Claus

Mathematics Subject Classification ID

Linear programming (90C05) Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25)

Related Items (2)

Unnamed Item ⋮ Unnamed Item

Cites Work

• On the configuration-LP for scheduling on unrelated machines
• Approximation algorithms for scheduling unrelated parallel machines
• A quasi-polynomial approximation for the restricted assignment problem
• Graph balancing: a special case of scheduling unrelated parallel machines
• The Santa Claus problem
• Santa claus meets hypergraph matchings
• On the Configuration-LP of the Restricted Assignment Problem
• Santa Claus Schedules Jobs on Unrelated Machines
• Quasi-Polynomial Local Search for Restricted Max-Min Fair Allocation
• Combinatorial Algorithm for Restricted Max-Min Fair Allocation

This page was built for publication: Compact LP Relaxations for Allocation Problems