Quasi-Polynomial Local Search for Restricted Max-Min Fair Allocation

DOI10.1145/2818695zbMath1398.68683arXiv1205.1373OpenAlexW1589729468MaRDI QIDQ4962210

Ola Svensson, Lukáš Poláček

Publication date: 30 October 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

linear programminglocal searchapproximation algorithmsmax-min fair allocation

Mathematics Subject Classification ID

Minimax problems in mathematical programming (90C47) Linear programming (90C05) Approximation methods and heuristics in mathematical programming (90C59) Discrete location and assignment (90B80) Approximation algorithms (68W25)

Related Items (5)

A note on the integrality gap of the configuration LP for restricted Santa Claus ⋮ Compact LP Relaxations for Allocation Problems ⋮ A Local-Search Algorithm for Steiner Forest ⋮ A Quasi-Polynomial Approximation for the Restricted Assignment Problem ⋮ Unnamed Item

This page was built for publication: Quasi-Polynomial Local Search for Restricted Max-Min Fair Allocation