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