Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp01c534fp06g
 Title: Approximation Algorithms for Network Routing and Facility Location Problems Authors: Li, Shi Advisors: Charikar, Moses Contributors: Computer Science Department Keywords: Approximation AlgorithmFacility Location ProblemNetwork Routing ProblemTheoretical Computer Science Subjects: Computer science Issue Date: 2014 Publisher: Princeton, NJ : Princeton University 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$. URI: http://arks.princeton.edu/ark:/88435/dsp01c534fp06g Alternate format: The Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the library's main catalog Type of Material: Academic dissertations (Ph.D.) Language: en Appears in Collections: Computer Science