University of Washington
Finding Structure in Entropy: Improved Approximation Algorithms for TSP and other Graph Problems
Abstract
dc:description.abstractThis dissertation demonstrates that there is an approximation algorithm for the metric traveling salesperson problem (TSP) with approximation ratio below 3/2. This represents the first improvement in nearly half a century, answering a long-standing open problem in combinatorial optimization. The algorithm we analyze, a variant of Christofides' 3/2 approximation from the 1970s, exploits a distribution over spanning trees that has as much entropy as possible subject to obeying certain marginal constraints. A key component of this work is to show that despite the inherent unpredictability of such a distribution, the trees it produces nevertheless exhibit surprisingly robust structural properties. To show these properties, we use that the generating polynomials of these distributions have a zero-free region in the complex plane, allowing us to employ a suite of tools coming from work on the geometry of polynomials. As a byproduct of our analysis, we prove several new statements that sharply characterize the behavior of such distributions. We also discuss several other results in network design, including a lower bound for this algorithm, an optimal rounding algorithm for a special case of TSP, and improved algorithms for the $k$-edge-connected multi-subgraph problem and the laminar thin tree problem.
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Klein, Nathan
- Advisors dc:contributor.advisor
-
- Karlin, Anna
- Oveis Gharan, Shayan
Subjects
dc:subject × 8Rights
dc:rights- Statement dc:rights
-
- none
- Language dc:language.iso
- en_US
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/1773/51140