Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Quasi-Polynomial Local Search for Restricted Max-Min Fair Allocation
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS. (Approximation algorithms)ORCID iD: 0000-0002-3204-146X
2012 (English)In: ICALP'12 Proceedings of the 39th international colloquium conference on Automata, Languages, and Programming - Volume Part I, Springer Berlin/Heidelberg, 2012, 726-737 p.Conference paper, Published paper (Refereed)
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. [1] proved that a certain configuration LP can be used to estimate the optimal value within a factor 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 because of 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 [1] 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
Springer Berlin/Heidelberg, 2012. 726-737 p.
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-111483DOI: 10.1007/978-3-642-31594-7_61ISI: 000342761000061Scopus ID: 2-s2.0-84883756966ISBN: 978-3-642-31593-0 (print)OAI: oai:DiVA.org:kth-111483DiVA: diva2:586621
Conference
39th international colloquium conference on Automata, Languages, and Programming, ICALP 2012
Note

QC 20130114

Available from: 2013-01-14 Created: 2013-01-12 Last updated: 2015-06-11Bibliographically approved

Open Access in DiVA

fulltext(397 kB)60 downloads
File information
File name FULLTEXT01.pdfFile size 397 kBChecksum SHA-512
7f241442e908138da62e9a85275b168f317b7ed6c72084a7469b05198acd4968eaabe0b821f0473f9cffef38dd8ca42fd44959d01e71559c28fb823295ffd8ec
Type fulltextMimetype application/pdf

Other links

Publisher's full textScopushttp://arxiv.org/abs/1205.1373

Authority records BETA

Polacek, Lukas

Search in DiVA

By author/editor
Polacek, Lukas
By organisation
Theoretical Computer Science, TCS
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 60 downloads
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

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 58 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf