**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Person# Lukas Polacek

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related units

Loading

Courses taught by this person

Loading

Related research domains

Loading

Related publications

Loading

People doing similar research

Loading

Related publications (6)

Loading

Loading

Loading

Courses taught by this person

No results

People doing similar research (135)

Related units (1)

Related research domains (3)

Approximation algorithm

In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable

Problem solving

Problem solving is the process of achieving a goal by overcoming obstacles, a frequent part of most activities. Problems in need of solutions range from simple personal tasks (e.g. how to turn on an a

Fermi problem

In physics or engineering education, a Fermi problem (or Fermi quiz, Fermi question, Fermi estimate), also known as a order-of-magnitude problem (or order-of-magnitude estimate, order estimation), i

Lukas Polacek, Ola Nils Anders Svensson

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 + 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 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 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.

Christos Kalaitzis, Aleksander Madry, Lukas Polacek, Ola Nils Anders Svensson

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. © 2014 Springer International Publishing Switzerland.

Christos Kalaitzis, Aleksander Madry, Lukas Polacek, Ola Nils Anders Svensson

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 to and also prove hardness of approximation results for both cases.