Restricted max-min allocation: integrality gap and approximation algorithm

DOI10.1007/S00453-022-00942-YzbMATH Open1494.91067OpenAlexW4214494873MaRDI QIDQ2149096FDOQ2149096

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

Recommendations

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

zbMATH Keywords

local searchapproximationintegrality gapfair allocation

Mathematics Subject Classification ID

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

Cites Work

• Approximation algorithms for scheduling unrelated parallel machines
• The Santa Claus problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• On Allocating Goods to Maximize Fairness
• MaxMin allocation via degree lower-bounded arborescences
• A condition for matchability in hypergraphs
• Santa claus meets hypergraph matchings
• New Constructive Aspects of the Lovász Local Lemma
• Restricted Max-Min Fair Allocation
• Quasi-polynomial local search for restricted max-min fair allocation
• Combinatorial Algorithm for Restricted Max-Min Fair Allocation
• A note on the integrality gap of the configuration LP for restricted Santa Claus
• Title not available (Why is that?)
• A Tale of Santa Claus, Hypergraphs and Matroids

Cited In (7)

• Restricted max-min fair allocations with inclusion-free intervals
• Technical Note—On Min-Max Integer Allocation Problems
• Polynomial-time combinatorial algorithm for general max-min fair allocation
• Quasi-polynomial local search for restricted max-min fair allocation
• Approximation Guarantees for Max Sum and Max Min Facility Dispersion with Parameterised Triangle Inequality and Applications in Result Diversification
• Minimization of Gini impurity: NP-completeness and approximation algorithm via connections with the \(k\)-means problem
• MaxMin allocation via degree lower-bounded arborescences

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)