Nathan Klein

Picture of Nathan

I'm an Assistant Professor at Boston University. Before that, I was a postdoc in the School of Mathematics at the Institute for Advanced Study. I completed my PhD at the University of Washington, where I was advised by Anna Karlin and Shayan Oveis Gharan. I am recruiting students, so if you are interested apply this Fall and feel free to reach out.

I mainly study approximation algorithms, with a focus on graph problems like the traveling salesperson problem (TSP). I am particularly interested in techniques to round solutions to linear programs. Here is my CV and my papers.


Recent papers:

Paper Description Coauthors Year
Ghost Value Augmentation for \(k\)-Edge-Connectivity We show every fractionally \(k\)-edge-connected weighted graph can be rounded to an integral \(k-O(1)\)-edge-connected graph of no greater cost. As a byproduct of this result we resolve a conjecture of Pritchard from 2010. Ellis Hershkowitz and Rico Zenklusen STOC 2024
From Trees to Polynomials and Back Again: New Capacity Bounds with Applications to TSP We show improved lower bounds on the capacity of a real stable polynomials based on its gradient. This leads to a streamlined analysis of the max entropy algorithm for TSP and a minor improvement of the approximation factor from \(\frac{3}{2}-10^{-36}\) to \(\frac{3}{2}-10^{-34}\). Leonid Gurvits and Jonathan Leake ICALP 2024
A Lower Bound for the Max Entropy Algorithm for TSP We show that the max entropy algorithm for TSP is no better than a 1.375 approximation, even in the graphic case. Therefore without further modifications the max entropy algorithm is unlikely to lead to a proof of the 4/3 conjecture. Billy Jin and David Williamson IPCO 2024
A Better-Than-1.6-Approximation for Prize-Collecting TSP We give a 1.599 approximation for prize-collecting TSP, a variant of TSP in which vertices can be excluded from the tour for an added penalty. This improves upon the recent 1.774 approximation of Blauth and Nägele. Jannis Blauth and Martin Nägele IPCO 2024

Selected Papers and Dissertation:

Paper Description Coauthors Year
Finding Structure in Entropy: Improved Approximation Algorithms for TSP and other Graph Problems My dissertation that pulls together the below three results (and some others as well) and has additional intuition and background. Many! 2023
A (Slightly) Improved Deterministic Approximation Algorithm for Metric TSP We show the first deterministic better-than-3/2 approximation algorithm for metric TSP. Anna Karlin and Shayan Oveis Gharan IPCO 2023
A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP We show that the integrality gap of the subtour polytope is bounded below 3/2. Anna Karlin and Shayan Oveis Gharan FOCS 2022
A (Slightly) Improved Approximation Algorithm for Metric TSP We show a randomized \(\frac{3}{2}-\epsilon\) approximation for metric TSP. Anna Karlin and Shayan Oveis Gharan STOC 2021

Teaching: CS 599: Rounding Techniques in Approximation Algorithms (Fall 2024)

Other writing: A short article on approximating TSP written for the general public

Fun: Concerning waffles / concerning primes / concerning math games

Contact

Email: nathanklein${the_4th_prime}11 at gmail dot com