A note on the integrality gap of the configuration LP for restricted Santa Claus

DOI10.1016/j.ipl.2020.106025zbMath1462.91011arXiv1807.03626OpenAlexW3087605022MaRDI QIDQ2203609

Klaus Jansen, Lars Rohwedder

Publication date: 7 October 2020

Published in: Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

analysis of algorithmsfair allocationconfiguration LP

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Linear programming (90C05) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Related Items (3)

Restricted max-min allocation: integrality gap and approximation algorithm ⋮ Unnamed Item ⋮ More on change-making and related problems

Cites Work

• A quasi-polynomial approximation for the restricted assignment problem
• 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: A note on the integrality gap of the configuration LP for restricted Santa Claus