Back to search

University of Washington

Finding Structure in Entropy: Improved Approximation Algorithms for TSP and other Graph Problems

Abstract

dc:description.abstract

This 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 × 8

Rights

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

Chain of custody

source
Harvested from
University of Washington
Base URL
digital.lib.washington.edu/server/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Klein, Nathan. Finding Structure in Entropy: Improved Approximation Algorithms for TSP and other Graph Problems. 2024. http://hdl.handle.net/1773/51140