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