Personne
Ola Nils Anders Svensson
Publications associées (49)
LP-Based Algorithms for Capacitated Facility Location
Ola Nils Anders Svensson, Hyung Chan An
Linear programming has played a key role in the study of algorithms for combinatorial optimization problems. In the field of approximation algorithms, this is well illustrated by the uncapacitated facility location problem. A variety of algorithmic methodo ...
IEEE2014On the Configuration LP for Maximum Budgeted Allocation
Ola Nils Anders Svensson, Christos Kalaitzis, Lukas Polacek, Aleksander Madry
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 integral ...
Springer2014Strong LP Formulations for Scheduling Splittable Jobs on Unrelated Machines
We study a natural generalization of the problem of minimizing makespan on unrelated machines in which jobs may be split into parts. The different parts of a job can be (simultaneously) processed on different machines, but each part requires a setup time b ...
Springer2014Overview of New Approaches for Approximating TSP
n this extended abstract, we survey some of the recent results on approximating the traveling salesman problem on graphic metrics.
We start by briefly explaining the algorithm of Oveis Gharan et al. [1] that has strong similarities to Christofides’ famo ...
Springer2013Single machine scheduling with scenarios
In the field of robust optimization, the goal is to provide solutions to combinatorial problems that hedge against variations of the numerical parameters. This constitutes an effort to design algorithms that are applicable in the presence of uncertainty in ...
2013Approximating k-median via pseudo-approximation
We present a novel approximation algorithm for k-median that achieves an approximation guarantee of 1 + √3 + ε, improving upon the decade-old ratio of 3+ε. Our approach is based on two components, each of which, we believe, is of independent interest. Firs ...
ACM Press2013Quasi-polynomial Local Search for Restricted Max-Min Fair Allocation
Ola Nils Anders Svensson, Lukas Polacek
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] pro ...
Springer2012Santa Claus Schedules Jobs On Unrelated Machines
One of the classic results in scheduling theory is the 2-approximation algorithm by Lenstra, Shmoys, and Tardos for the problem of scheduling jobs to minimize makespan on unrelated machines; i.e., job j requires time p(ij) if processed on machine i. More t ...
Siam Publications2012Tight Approximation Algorithms for Scheduling with Fixed Jobs and Nonavailability
Ola Nils Anders Svensson, Klaus Jansen
We study two closely related problems in nonpreemptive scheduling of jobs on identical parallel machines. In these two settings there are either fixed jobs or nonavailability intervals during which the machines are not available; in both cases, the objecti ...
Assoc Computing Machinery2012Hardness of Vertex Deletion and Project Scheduling
Assuming the Unique Games Conjecture, we show strong inapproximability results for two natural vertex deletion problems on directed graphs: for any integer k ≥ 2 and arbitrary small ε > 0, the Feedback Vertex Set problem and the DAG Vertex Deletion problem ...
Springer2012