Abstract
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 n O(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.
A full version of this paper is available at http://arxiv.org/abs/1205.1373 . This research was supported by ERC Advanced investigator grants 228021 and 226203.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Asadpour, A., Feige, U., Saberi, A.: Santa claus meets hypergraph matchings. In: Proceedings of the 11th International Workshop and 12th International Workshop on Approximation, Randomization and Combinatorial Optimization, pp. 10–20 (2008); see authors’ homepages for the lower bound of 1/4 instead of the claimed 1/5 in the conference version
Asadpour, A., Saberi, A.: An approximation algorithm for max-min fair allocation of indivisible goods. In: Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, STOC 2007, pp. 114–121. ACM, New York (2007)
Bansal, N., Sviridenko, M.: The santa claus problem. In: Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, STOC 2006, pp. 31–40. ACM Press, New York (2006)
Bateni, M., Charikar, M., Guruswami, V.: Maxmin allocation via degree lower-bounded arborescences. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, pp. 543–552. ACM, New York (2009)
Bezáková, I., Dani, V.: Allocating indivisible goods. SIGecom. Exch. 5, 11–18 (2005)
Chakrabarty, D., Chuzhoy, J., Khanna, S.: On allocating goods to maximize fairness. In: Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science FOCS 2009, pp. 107–116. IEEE Computer Society Press, Washington, DC (2009)
Dobzinski, S., Schapira, M.: An improved approximation algorithm for combinatorial auctions with submodular bidders. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, SODA 2006, pp. 1064–1073. ACM, New York (2006)
Feige, U.: On maximizing welfare when utility functions are subadditive. In: Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, STOC 2006, pp. 41–50. ACM, New York (2006)
Feige, U.: On allocations that maximize fairness. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, pp. 287–293. Society for Industrial and Applied Mathematics, Philadelphia (2008)
Feige, U.: On estimation algorithms vs approximation algorithms. In: Hariharan, R., Mukund, M., Vinay, V. (eds.) IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2008). Leibniz International Proceedings in Informatics (LIPIcs), vol. 2, pp. 357–363. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2008)
Feige, U., Vondrak, J.: Approximation algorithms for allocation problems: Improving the factor of 1 - 1/e. In: 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006, pp. 667–676 (October 2006)
Haeupler, B., Saha, B., Srinivasan, A.: New constructive aspects of the lovasz local lemma. In: 2010 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 397–406 (October 2010)
Lenstra, J.K., Shmoys, D.B., Tardos, É.: Approximation algorithms for scheduling unrelated parallel machines. Math. Program. 46, 259–271 (1990)
Svensson, O.: Santa claus schedules jobs on unrelated machines. In: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, STOC 2011, pp. 617–626. ACM, New York (2011)
Vondrak, J.: Optimal approximation for the submodular welfare problem in the value oracle model. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, STOC 2008, pp. 67–74. ACM, New York (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Polacek, L., Svensson, O. (2012). Quasi-polynomial Local Search for Restricted Max-Min Fair Allocation. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds) Automata, Languages, and Programming. ICALP 2012. Lecture Notes in Computer Science, vol 7391. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-31594-7_61
Download citation
DOI: https://doi.org/10.1007/978-3-642-31594-7_61
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-31593-0
Online ISBN: 978-3-642-31594-7
eBook Packages: Computer ScienceComputer Science (R0)