Steiner Tree Approximation via Iterative Randomized Rounding

The Steiner tree problem is one of the most fundamental NP-hard problems: given a weighted undirected graph and a subset of terminal nodes, find a minimum-cost tree spanning the terminals. In a sequence of papers, the approximation ratio for this problem was improved from 2 to 1.55 [Robins,Zelikovsky-'05]. All these algorithms are purely combinatorial. A long-standing open problem is whether there is an LP relaxation of Steiner tree with integrality gap smaller than 2 [Vazirani,Rajagopalan-'99]. In this paper we present an LP-based approximation algorithm for Steiner tree with an improved approximation factor. Our algorithm is based on a, seemingly novel, \emph{iterative randomized rounding} technique. We consider an LP relaxation of the problem, which is based on the notion of directed components. We sample one component with probability proportional to the value of the associated variable in a fractional solution: the sampled component is contracted and the LP is updated consequently. We iterate this process until all terminals are connected. Our algorithm delivers a solution of cost at most ln(4)+\eps

An Improved LP-based Approximation for Steiner Tree

Thomas Rothvoss, Laura Sanità

The Steiner tree problem is one of the most fundamental

\mathbf{NP}

-hard problems: given a weighted undirected graph and a subset of terminal nodes, find a minimum-cost tree spanning the terminals. In a sequence of papers, the approximation ratio for this problem was improved from

2

to the current best

1.55

[Robins,Zelikovsky-SIDMA'05]. All these algorithms are purely combinatorial. A long-standing open problem is whether there is an LP-relaxation for Steiner tree with integrality gap smaller than

2

[Vazirani,Rajagopalan-SODA'99]. In this paper we improve the approximation factor for Steiner tree, developing an LP-based approximation algorithm. Our algorithm is based on a, seemingly novel, \emph{iterative randomized rounding} technique. We consider a directed-component cut relaxation for the

k

-restricted Steiner tree problem. We sample one of these components with probability proportional to the value of the associated variable in the optimal fractional solution and contract it. We iterate this process for a proper number of times and finally output the sampled components together with a minimum-cost terminal spanning tree in the remaining graph. Our algorithm delivers a solution of cost at most

\ln(4)

times the cost of an optimal

k

-restricted Steiner tree. This directly implies a $\ln(4)+\varepsilon

Acm Order Department, P O Box 64145, Baltimore, Md 21264 Usa2010

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

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.

Assoc Computing Machinery2016

Applications of Strong Convex Relaxations to Allocation Problems

Christos Kalaitzis

Approximation algorithms are a commonly used tool for designing efficient algorithmic solutions for intractable problems, at the expense of the quality of the output solution. A prominent technique for designing such algorithms is the use of Linear Programming (LP) relaxations. An optimal solution to such a relaxation provides a bound on the objective value of the optimal integral solution, to which we compare the integral solution we return. In this context, when studying a specific problem, two natural questions often arise: What is a strong LP relaxation for this problem, and how can we exploit it? Over the course of the past few decades, a significant amount of effort has been expended by the research community in order to answer these questions for a variety of interesting intractable problems. Although there exist multiple problems for which we have designed LP relaxations that achieve best-possible guarantees, there still exist numerous problems for which we either have no strong LP relaxations, or do not know how to use them. The main focus of this thesis is extending our understanding of such strong relaxations. We focus on designing good approximation algorithms for certain allocation problems, by employing a class of strong LP relaxations, called configuration-LPs. For many such allocation problems, the best-known results are derived by using simple and natural LP relaxations, whereas configuration-LPs have been used successfully on several occasions in order to break pre-existing barriers set by weaker relaxations. However, our understanding of configuration-LPs is far from complete for many problems. Therefore, understanding and using these relaxations to the farthest extent possible is a quite intriguing question. Answering this question could result in improved approximation algorithms for a wide variety of allocation problems. The first problem we address in this thesis is the restricted max-min fair allocation problem. Prior to our work, the best known result provided an

\Omega(1)

-approximation that ran in polynomial time. Also, it was known how to estimate the value of an optimal solution to the problem within a factor of

1/(4+c)

, for any

c>0

, by solving the corresponding configuration-LP. Our first contribution in this thesis is the design of a

1/13

-approximation algorithm for the problem, using the configuration-LP. Specifically, although our algorithm is fully combinatorial, it consists of a local-search procedure that is guaranteed to succeed only when the configuration-LP is feasible. In order to establish the correctness and running time of the algorithm, it is crucial to use the configuration-LP in our analysis. The second problem we study is the scheduling of jobs on unrelated machines in order to minimize the sum of weighted completion times. For this problem, the best known approximation algorithm achieves a ratio of

3/2-r

, for some small

r>0

. Our second contribution in this thesis is the improvement of this ratio to

(1+\sqrt{2})/2+c

, for any

c>0

, for the special case of the problem where the jobs have uniform Smith ratios. To achieve this ratio, we design a randomized rounding algorithm that rounds solutions to the corresponding configuration-LP. Through a careful examination of the distribution this randomized algorithm outputs, we identify the one that maximizes the approximation ratio, and we then upper bound the ratio this worst-case distribution exhibits by

(1+\sqrt{2})/2+c

EPFL2017

Applications of Strong Convex Relaxations to Allocation Problems

Christos Kalaitzis

\Omega(1)

-approximation that ran in polynomial time. Also, it was known how to estimate the value of an optimal solution to the problem within a factor of

1/(4+c)

, for any

c>0

, by solving the corresponding configuration-LP. Our first contribution in this thesis is the design of a

1/13

3/2-r

, for some small

r>0

. Our second contribution in this thesis is the improvement of this ratio to

(1+\sqrt{2})/2+c

, for any

c>0

(1+\sqrt{2})/2+c

EPFL2017

An Improved LP-based Approximation for Steiner Tree

Thomas Rothvoss, Laura Sanità

The Steiner tree problem is one of the most fundamental

\mathbf{NP}

2

to the current best

1.55

[Robins,Zelikovsky-SIDMA'05]. All these algorithms are purely combinatorial. A long-standing open problem is whether there is an LP-relaxation for Steiner tree with integrality gap smaller than

2

k

\ln(4)

times the cost of an optimal

k

-restricted Steiner tree. This directly implies a $\ln(4)+\varepsilon

Acm Order Department, P O Box 64145, Baltimore, Md 21264 Usa2010