Approximation Algorithms for Network Routing and Facility Location Problems

Abstract:

We study approximation algorithms for two classes of optimization problems.

The first class is network routing problems. These are an important class of optimization problems, among which the edge-disjoint paths (\EDP) problem is one of the central and most extensively studied. In the first part of my thesis, I will give a poly-logarithmic approximation for \EDP with congestion 2. This culminates a long line of research on the \EDP with congestion problem.

The second class is facility location problems. Two important problems in this class are uncapacitated facility location (\UFL) and $k$-median, both having long histories and numerous applications. We give improved approximation ratios for both problems in the second part of my thesis.

For \UFL, we present a 1.488-approximation algorithm for the metric uncapacitated facility location (UFL) problem. The previous best algorithm, due to Byrka, gave a 1.5-approximation for \UFL. His algorithm is parametrized by $\gamma$ whose value is set to a fixed number. We show that if $\gamma$ is randomly selected, the approximation ratio can be improved to 1.488.

For $k$-median, we present an improved approximation algorithm for $k$-median. Our algorithm, which gives a $1+\sqrt 3+\epsilon$-approximation for $k$-median, is based on two rather surprising components. First, we show that it suffices to find an $\alpha$-approximate solution that contains $k+O(1)$ medians. Second, we give such a pseudo-approximation algorithm with $\alpha=1+\sqrt 3+\epsilon$.