We study the Maximum Budgeted Allocation problem, i.e., the problem of selling a set of m indivisible goods to n players, each with a separate budget, such that we maximize the collected revenue. Since the natural assignment LP is known to have an integrality gap of, which matches the best known approximation algorithms, our main focus is to improve our understanding of the stronger configuration LP relaxation. In this direction, we prove that the integrality gap of the configuration LP is strictly better than, and provide corresponding polynomial time roundings, in the following restrictions of the problem: (i) the Restricted Budgeted Allocation problem, in which all the players have the same budget and every item has the same value for any player it can be sold to, and (ii) the graph MBA problem, in which an item can be assigned to at most 2 players. Finally, we improve the best known upper bound on the integrality gap for the general case from 5/6 to 2√2 2 ≈ 0.828 and also prove hardness of approximation results for both cases.
We study the maximum budgeted allocation problem, i.e., the problem of selling a set of m indivisible goods to n players, each with a separate budget, such that we maximize the collected revenue. Since the natural assignment LP is known to have an integrality gap of (Formula presented.), which matches the best known approximation algorithms, our main focus is to improve our understanding of the stronger configuration LP relaxation. In this direction, we prove that the integrality gap of the configuration LP is strictly better than (Formula presented.), and provide corresponding polynomial time roundings, in the following restrictions of the problem: (i) the restricted budgeted allocation problem, in which all the players have the same budget and every item has the same value for any player it can be sold to, and (ii) the graph MBA problem, in which an item can be assigned to at most 2 players. Finally, we improve the best known upper bound on the integrality gap for the general case from (Formula presented.) and also prove hardness of approximation results for both cases.
In the past decades, linear programming (LP) has been successfully used to develop approximation algorithms for various optimization problems. In particular, the so-called assignment LP has lead to substantial progress for various allocation problems, including scheduling unrelated parallel machines. However, we have reached its limits for many problems, since the best-known approximation algorithms match the integrality gap of the assignment LP for these problems.
The natural question is then whether a different LP formulation can lead to better algorithms. We answer this question positively for variants of two allocation problems: max-min fair allocation and maximum budgeted allocation. This is achieved by using a more powerful LP formulation called the configuration LP that has an exponential number of variables, but can be approximated in polynomial time.
The restricted max-min fair allocation problem, also known as the restricted Santa Claus problem, is one of few problems that have a better polynomial estimation algorithm than approximation algorithm. An estimation algorithm estimates the value of the optimal solution, but is not necessarily able to find the optimal solution. The configuration LP can be used to estimate the optimal value within a factor of 1/(4+ɛ) for any ɛ>0, but it is only known how to efficiently find a solution achieving this value in exponential time. We give an approximation algorithm with the same approximation ratio but improve the running time to quasi-polynomial: 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.
For the maximum budgeted allocation (MBA) the integrality gap of the assignment LP is exactly 3/4. We prove that the integrality gap of the configuration LP is strictly better than 3/4 and provide corresponding polynomial time rounding algorithms for two variants of the problem: the restricted MBA and the graph MBA. Finally, we improve the best-known upper bound on the integrality gap for the general case from 0.833 to 0.828 and also show hardness of approximation results for both variants studied.
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.
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.