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

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 |

Files in This Item:

File | Description | Size | Format | |
---|---|---|---|---|

Li_princeton_0181D_10850.pdf | 809.44 kB | Adobe PDF | View/Download |

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