Nathan Klein

List of research outcomes

This list is not complete and representing at the moment only items from zbMATH Open and arXiv. We are working on additional sources - please check back here soon!

Publication	Date of Publication	Type
Ghost Value Augmentation for k-Edge-Connectivity (available as arXiv preprint)	N/A	Paper
Maximum entropy is a 10/7-approximation algorithm for the TSP on half-integral cycle cut instances Operations Research Letters	2026-09-14	Paper
A randomized rounding approach for DAG edge deletion	2026-09-11	Paper
Dual charging for half-integral TSP	2026-09-11	Paper
A better-than-1.6-approximation for prize-collecting TSP Mathematical Programming. Series A. Series B	2026-05-08	Paper
A lower bound for the max entropy algorithm for TSP Mathematical Programming. Series A. Series B	2026-05-08	Paper
From trees to polynomials and back again: new capacity bounds with applications to TSP	2026-01-14	Paper
Thin trees for laminar families	2025-08-15	Paper
A (slightly) improved bound on the integrality gap of the subtour LP for TSP	2025-08-15	Paper
A \(\frac{4}{3} \)-approximation algorithm for half-integral cycle cut instances of the TSP Mathematical Programming. Series A. Series B	2025-03-05	Paper
A lower bound for the max entropy algorithm for TSP	2025-02-07	Paper
A better-than-1.6-approximation for prize-collecting TSP	2025-02-07	Paper
A (slightly) improved approximation algorithm for metric TSP Operations Research	2025-01-30	Paper
Matroid partition property and the secretary problem	2024-09-25	Paper
An improved approximation algorithm for the minimum <i>k</i> -edge connected multi-subgraph problem Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing	2023-12-08	Paper
From Trees to Polynomials and Back Again: New Capacity Bounds with Applications to TSP	2023-11-15	Paper
A (slightly) improved approximation algorithm for metric TSP Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing	2023-11-14	Paper
A 4/3-approximation algorithm for half-integral cycle cut instances of the TSP Integer Programming and Combinatorial Optimization	2023-11-09	Paper
A deterministic better-than-3/2 approximation algorithm for metric TSP Integer Programming and Combinatorial Optimization	2023-11-09	Paper
A Lower Bound for the Max Entropy Algorithm for TSP	2023-11-03	Paper
Matroid Partition Property and the Secretary Problem	2021-11-24	Paper
A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP	2021-05-20	Paper
An improved approximation algorithm for TSP in the half integral case Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing	2021-01-19	Paper
An Improved Approximation Algorithm for TSP in the Half Integral Case (available as arXiv preprint)	2019-08-01	Paper

Research outcomes over time

This page was built for person: Nathan Klein