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. / Under de senaste decennierna har linjärprogrammering (LP) framgångsrikt använts för att utveckla approximeringsalgoritmer. I synnerhet har det så kallade tilldelnings-LP lett till betydande framsteg för olika allokeringsproblem, som scheduling unrelated parallel machines. Vi verkar dock ha nått dess gräns, eftersom de bästa approximeringsalgoritmerna har samma kvalitet som heltalsgapet för dessa problem. Den naturliga frågan är då om någon annan LP-formulering kan leda till bättre algoritmer. Vi besvarar denna fråga positivt för varianter av två fördelningsproblem: max-min fair allocation och maximal budgeted allocation. Vi använder en mer kraftfull LP-formulering som kallas konfigurations-LP och har ett exponentiellt antal variabler men kan approximeras i polynomisk tid. Problemet restricted max-min fair allocation, som är även känt som restricted Santa Claus problem, är ett av få problem som har en bättre polynomisk värderingsalgoritm än approximeringsalgoritm. En värderingsalgoritm approximerar det optimala värdet, men hittar inte nödvändigtvis den optimala lösningen. Konfigurations-LP kan användas för att approximera det optimala värdet inom en faktor 1 / (4 + ɛ) för något ɛ > 0, men man vet bara hur man hittar en lösning med sådan kvalitet i exponentiellt tid. Vi ger en approximeringsalgoritm med samma approximeringskvalitet men förbättrar tidskomplexitet till kvasipolynomisk: n^O(log n). Våra tekniker har också den intressanta egenskapen att även om vi använder det ganska komplext konfigurations-LP:t i analysen, löser vi aldrig det och vår algoritm är rent kombinatorisk. För maximal budgeted allocation (MBA) är heltalsgapet av tilldelnings-LP:et är precis 3/4. Vi bevisar att heltalsgapet av konfiguration-LP är strikt bättre än 3/4 och vi ger en motsvarande polynomisk avrundningsalgoritm för två varianter av problemet: restricted MBA och graph MBA. Slutligen förbättrar vi den bäst kända övre gränsen på heltalsgapet för det allmänna fallet från 0.833 till 0.828 samt ger approximeringssvårighetsresultat för båda två studerade varianter. / <p>QC 20150305</p> / ERC APPROXNP 226203
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-160869 |
| Date | January 2015 |
| Creators | Polacek, Lukas |
| Publisher | KTH, Teoretisk datalogi, TCS, Stockholm |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | English |
| Type | Licentiate thesis, monograph, info:eu-repo/semantics/masterThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | TRITA-CSC-A, 1653-5723 ; 2015:02 |
Page generated in 0.0021 seconds