Blog
About

42
views
1
recommends
+1 Recommend
1 collections
    8
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

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

      Preprint

      ,

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          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. proved that a certain configuration LP can be used to estimate the optimal value within a factor \({1}/{(4+\epsilon)}\), for any \(\epsilon>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 Asadpour et al. and provide a novel analysis that lets us significantly improve the bound on its running time: from \(2^{O(n)}\) to \(n^{O(\log n)}\). 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.

          Related collections

          Most cited references 11

          • Record: found
          • Abstract: not found
          • Article: not found

          Approximation algorithms for scheduling unrelated parallel machines

            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            Optimal approximation for the submodular welfare problem in the value oracle model

             Jan Vondrák (2008)
              Bookmark
              • Record: found
              • Abstract: not found
              • Article: not found

              The Santa Claus problem

                Bookmark

                Author and article information

                Journal
                07 May 2012
                2014-01-17
                1205.1373

                http://arxiv.org/licenses/nonexclusive-distrib/1.0/

                Custom metadata
                68Q25
                14 pages, 1 figure
                cs.DS

                Comments

                Comment on this article