Change search
ReferencesLink to record
Permanent link

Direct link
Quasi-polynomial local search for restricted max-min fair allocation
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.ORCID iD: 0000-0002-3204-146X
2015 (English)In: ACM Transactions on Algorithms, ISSN 1549-6325, E-ISSN 1549-6333, Vol. 12, no 2, 13Article in journal (Refereed) PublishedText
Abstract [en]

The restricted max-min fair allocation problem (also known as the restricted Santa Claus problem) is one of few problems that enjoys the intriguing status of having a better estimation algorithm than approximation algorithm. Indeed, Asadpour et al. [2012] proved that a certain configuration LP can be used to estimate the optimal value within a factor of 1/(4 + ε), for any ε > 0, but at the same time it is not known how to efficiently find a solution with a comparable performance guarantee. A natural question that arises from their work is if the difference between these guarantees is inherent or results from a lack of suitable techniques. We address this problem by giving a quasi-polynomial approximation algorithm with the mentioned performance guarantee. More specifically, we modify the local search of Asadpour et al. [2012] and provide a novel analysis that lets us significantly improve the bound on its running time: from 2O(N) to nO(LOGN). Our techniques also have the interesting property that although we use the rather complex configuration LP in the analysis, we never actually solve it and therefore the resulting algorithm is purely combinatorial.

Place, publisher, year, edition, pages
Association for Computing Machinery (ACM), 2015. Vol. 12, no 2, 13
Keyword [en]
Approximation algorithms, Linear programming, Local search, Max-min fair allocation, Algorithms, Local search (optimization), Polynomial approximation, Complex configuration, Estimation algorithm, Fair allocation, Optimal values, Performance guarantees, Quasi-poly-nomial, Running time
National Category
Computer Systems
URN: urn:nbn:se:kth:diva-181228DOI: 10.1145/2818695ScopusID: 2-s2.0-84947911532OAI: diva2:902839

QC 20160212

Available from: 2016-02-12 Created: 2016-01-29 Last updated: 2016-02-12Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Poláček, Lukas
By organisation
Theoretical Computer Science, TCS
In the same journal
ACM Transactions on Algorithms
Computer Systems

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 59 hits
ReferencesLink to record
Permanent link

Direct link