Restricted max-min allocation: integrality gap and approximation algorithm

DOI10.1007/S00453-022-00942-YMaRDI QIDQ2149096zbMATH OpenOpenAlexFDO

Authors Siu-Wing Cheng, Yuchen Mao

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

approximationfair allocationintegrality gaplocal search

Mathematics Subject Classification ID

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

Recommendations

• Restricted Max-Min Fair Allocation
• Combinatorial algorithm for restricted max-min fair allocation
• Combinatorial Algorithm for Restricted Max-Min Fair Allocation
• On (1,)-restricted max-min fair allocation problem
• On \((1, \epsilon )\)-restricted max-min fair allocation problem

Cites work

• A condition for matchability in hypergraphs
• A note on the integrality gap of the configuration LP for restricted Santa Claus
• A Tale of Santa Claus, Hypergraphs and Matroids
• Approximation algorithms for scheduling unrelated parallel machines
• Combinatorial algorithm for restricted max-min fair allocation
• scientific article; zbMATH DE number 5485443 (Why is no real title available?)
• scientific article; zbMATH DE number 5764883 (Why is no real title available?)
• MaxMin allocation via degree lower-bounded arborescences
• New constructive aspects of the Lovász local lemma
• On allocating goods to maximize fairness
• Quasi-polynomial local search for restricted max-min fair allocation
• Restricted max-min allocation: approximation and integrality gap
• Restricted Max-Min Fair Allocation
• Santa claus meets hypergraph matchings
• The Santa Claus problem

Cited in

(15)

• Minimization of Gini impurity: NP-completeness and approximation algorithm via connections with the \(k\)-means problem
• Multistage online maxmin allocation of indivisible entities
• Quasi-polynomial local search for restricted max-min fair allocation
• Restricted max-min fair allocations with inclusion-free intervals
• Technical Note—On Min-Max Integer Allocation Problems
• On (1,)-restricted max-min fair allocation problem
• Quasi-polynomial local search for restricted max-min fair allocation
• Combinatorial algorithm for restricted max-min fair allocation
• Restricted max-min allocation: approximation and integrality gap
• MaxMin allocation via degree lower-bounded arborescences
• Approximation Guarantees for Max Sum and Max Min Facility Dispersion with Parameterised Triangle Inequality and Applications in Result Diversification
• Polynomial-time combinatorial algorithm for general max-min fair allocation
• A geometric programming approach to solve the restricted assignment case of the Santa Claus problem
• Scheduling splittable jobs on configurable machines
• On \((1, \epsilon )\)-restricted max-min fair allocation problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2149096)