Skip navigation
Please use this identifier to cite or link to this item:
Title: Approximation Algorithms for Network Routing and Facility Location Problems
Authors: Li, Shi
Advisors: Charikar, Moses
Contributors: Computer Science Department
Keywords: Approximation Algorithm
Facility Location Problem
Network Routing Problem
Theoretical 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$.
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

Files in This Item:
File Description SizeFormat 
Li_princeton_0181D_10850.pdf809.44 kBAdobe PDFView/Download

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.