Santa claus meets hypergraph matchings
From MaRDI portal
Publication:3189065
DOI10.1145/2229163.2229168zbMath1295.05165OpenAlexW2001927417MaRDI QIDQ3189065
Arash Asadpour, Amin Saberi, Uriel Feige
Publication date: 9 September 2014
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2229163.2229168
Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Discrete location and assignment (90B80) Graph algorithms (graph-theoretic aspects) (05C85) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)
Related Items
Approximating the Nash Social Welfare with Indivisible Items ⋮ Matching orderable and separable hypergraphs ⋮ Restricted max-min allocation: integrality gap and approximation algorithm ⋮ Perfect matching in bipartite hypergraphs subject to a demand graph ⋮ Strong LP formulations for scheduling splittable jobs on unrelated machines ⋮ Polynomial-time combinatorial algorithm for general max-min fair allocation ⋮ A note on the integrality gap of the configuration LP for restricted Santa Claus ⋮ General max-min fair allocation ⋮ Compact LP Relaxations for Allocation Problems ⋮ A Quasi-Polynomial Approximation for the Restricted Assignment Problem ⋮ On the configuration-LP for scheduling on unrelated machines ⋮ Restricted Max-Min Fair Allocation ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On \((1, \epsilon )\)-restricted max-min fair allocation problem ⋮ Finding independent transversals efficiently ⋮ Lazy Local Search Meets Machine Scheduling ⋮ Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines
