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 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.
Teaching:
- CS 530: Advanced Algorithms (Fall 2025)
- CS 237: Probability in Computing (Spring 2025, co-taught with Tiago Januario)
- CS 599: Rounding Techniques in Approximation Algorithms (Fall 2024)
Students:
- Zhuan Khye Koh, postdoc
Recent papers:
| Paper | Description | Coauthors | Year |
|---|---|---|---|
| A Randomized Rounding Approach for DAG Edge Deletion | In the DAG Edge Deletion problem, we are given an edge-weighted DAG and a parameter \(k\) and want to delete the minimum weight set of edges so that no paths of length \(k\) remain. We give a \(0.549(k+1)\) approximation, improving upon \(\frac{2}{3}(k+1)\). | Sina Kalantarzadeh and Victor Reis | APPROX 2025 |
| Dual Charging for Half-Integral TSP | We show that the max entropy algorithm for TSP is a 1.49776 approximation in the half integral case, improving upon the previous known bound of 1.49993. This also improves upon the 1.49842 approximation from Gupta et al. which uses a different algorithm. Our improvement comes from using the dual, instead of the primal, to analyze the expected cost of the matching. | Mehrshad Taziki | APPROX 2025 |
| 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. We also obtain a 1.6662 approximation for the path version of PCTSP, improving upon 1.926. | 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 |
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