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 gamesContact
Email: nathanklein${the_4th_prime}11 at gmail dot com