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 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:

Students:

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 games

Contact

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