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 237: Probability in Computing (Spring 2026, co-taught with Tiago Januario)
- 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:
- Pooria Jalali Farahani
- Logan Grout
- Zi Song Yeoh (co-advised with Krzysztof Onak)
Recent papers:
| Paper | Description | Coauthors | Year |
|---|---|---|---|
| Maximum Entropy is a 10/7-Approximation Algorithm for the TSP on Half-Integral Cycle Cut Instances | We demonstrate that the max entropy algorithm for TSP is a 10/7 approximation for half integral cycle cut instances. This is the first non-trivial class of instances max entropy has been shown to be a better-than-1.49 approximation for. | Billy Jin and David Williamson | OR Letters 2026 |
| Thin Trees for Near Minimum Cuts | We show that every \(k\)-edge-connected graph contains a tree which is \(O(1/k)\) thin with respect to its near minimum cuts. In other words, we construct a tree with at most \(O(1)\) edges across every near minimum cut of the graph. | Neil Olver and Zi Song Yeoh | ICALP 2026 |
| A Strong Linear Programming Relaxation for Weighted Tree Augmentation | We give a 1.49 approximation algorithm for the weighted tree augmentation problem by rounding a strong LP relaxation. This goes below the integrality gap of the cut LP and improves over the local-search based \(1.5+\epsilon\) approximation of Traub and Zenklusen. | Vincent Cohen-Addad, Marina Drygala, and Ola Svensson | STOC 2026 |
| 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 |
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 |
Past Students:
- Zhuan Khye Koh, postdoc, now Assistant Professor at UBC Sauder.
- Steve Choi, undergrad, now PhD student at Waterloo
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