Restricted max-min allocation: integrality gap and approximation algorithm

DOI10.1007/s00453-022-00942-yzbMath1494.91067OpenAlexW4214494873MaRDI QIDQ2149096

Yuchen Mao, Siu-Wing Cheng

Publication date: 28 June 2022

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-022-00942-y

zbMATH Keywords

approximationlocal searchintegrality gapfair allocation

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Related Items (1)

Polynomial-time combinatorial algorithm for general max-min fair allocation

Cites Work

• Approximation algorithms for scheduling unrelated parallel machines
• A condition for matchability in hypergraphs
• A note on the integrality gap of the configuration LP for restricted Santa Claus
• Quasi-polynomial Local Search for Restricted Max-Min Fair Allocation
• The Santa Claus problem
• Santa claus meets hypergraph matchings
• Combinatorial Algorithm for Restricted Max-Min Fair Allocation
• Restricted Max-Min Fair Allocation
• A Tale of Santa Claus, Hypergraphs and Matroids
• On Allocating Goods to Maximize Fairness
• MaxMin allocation via degree lower-bounded arborescences
• New Constructive Aspects of the Lovász Local Lemma
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Restricted max-min allocation: integrality gap and approximation algorithm