Nathan Klein

36 papers A* 7A 4B 4Misc 1Journal 18Unranked 1
YearRankTypeTitle / Venue / Authors
2026 J jnl
A Strong Linear Programming Relaxation for Weighted Tree Augmentation.
CoRR
Vincent Cohen-Addad, Marina Drygala, Nathan Klein, Ola Svensson
2025 J jnl
A $\frac{4}{3}$-approximation algorithm for half-integral cycle cut instances of the TSP.
Math. Program.
Billy Jin, Nathan Klein, David P. Williamson
2025 A conf
A Randomized Rounding Approach for DAG Edge Deletion.
APPROX/RANDOM
Sina Kalantarzadeh, Nathan Klein, Victor Reis
2025 J jnl
A Randomized Rounding Approach for DAG Edge Deletion.
CoRR
Sina Kalantarzadeh, Nathan Klein, Victor Reis
2025 A conf
Dual Charging for Half-Integral TSP.
APPROX/RANDOM
Nathan Klein, Mehrshad Taziki
2025 J jnl
Dual Charging for Half-Integral TSP.
CoRR
Nathan Klein, Mehrshad Taziki
2024 J jnl
A (Slightly) Improved Approximation Algorithm for Metric TSP.
Oper. Res.
Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan
2024 B conf
A Better-Than-1.6-Approximation for Prize-Collecting TSP.
IPCO
Jannis Blauth, Nathan Klein, Martin Nägele
2024 B conf
A Lower Bound for the Max Entropy Algorithm for TSP.
IPCO
Billy Jin, Nathan Klein, David P. Williamson
2024 — —
Finding Structure in Entropy: Improved Approximation Algorithms for TSP and other Graph Problems
Nathan Klein
2024 A* conf
From Trees to Polynomials and Back Again: New Capacity Bounds with Applications to TSP.
ICALP
Leonid Gurvits, Nathan Klein, Jonathan Leake
2024 A* conf
Ghost Value Augmentation for k-Edge-Connectivity.
STOC
D. Ellis Hershkowitz, Nathan Klein, Rico Zenklusen
2023 B conf
A 4/3-Approximation Algorithm for Half-Integral Cycle Cut Instances of the TSP.
IPCO
Billy Jin, Nathan Klein, David P. Williamson
2023 J jnl
A Better-Than-1.6-Approximation for Prize-Collecting TSP.
CoRR
Jannis Blauth, Nathan Klein, Martin Nägele
2023 B conf
A Deterministic Better-than-3/2 Approximation Algorithm for Metric TSP.
IPCO
Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan
2023 J jnl
A Lower Bound for the Max Entropy Algorithm for TSP.
CoRR
Billy Jin, Nathan Klein, David P. Williamson
2023 J jnl
From Trees to Polynomials and Back Again: New Capacity Bounds with Applications to TSP.
CoRR
Leonid Gurvits, Nathan Klein, Jonathan Leake
2023 J jnl
From Trees to Polynomials and Back Again: New Capacity Bounds with Applications to TSP.
Electron. Colloquium Comput. Complex.
Leonid Gurvits, Nathan Klein, Jonathan Leake
2023 J jnl
Ghost Value Augmentation for k-ECSS and k-ECSM.
CoRR
D. Ellis Hershkowitz, Nathan Klein, Rico Zenklusen
2023 A conf
Matroid Partition Property and the Secretary Problem.
ITCS
Dorna Abdolazimi, Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan
2023 A* conf
Thin Trees for Laminar Families.
FOCS
Nathan Klein, Neil Olver
2023 J jnl
Thin trees for laminar families.
CoRR
Nathan Klein, Neil Olver
2022 A* conf
A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP.
FOCS
Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan
2022 J jnl
A (Slightly) Improved Deterministic Approximation Algorithm for Metric TSP.
CoRR
Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan
2022 J jnl
A 4/3-Approximation Algorithm for Half-Integral Cycle Cut Instances of the TSP.
CoRR
Billy Jin, Nathan Klein, David P. Williamson
2022 A* conf
An improved approximation algorithm for the minimum
STOC
Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan, Xinzhi Zhang
2021 J jnl
A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP.
CoRR
Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan
2021 A* conf
A (slightly) improved approximation algorithm for metric TSP.
STOC
Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan
2021 J jnl
An Improved Approximation Algorithm for the Minimum k-Edge Connected Multi-Subgraph Problem.
CoRR
Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan, Xinzhi Zhang
2021 J jnl
Matroid Partition Property and the Secretary Problem.
CoRR
Dorna Abdolazimi, Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan
2020 J jnl
A (Slightly) Improved Approximation Algorithm for Metric TSP.
CoRR
Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan
2020 A* conf
An improved approximation algorithm for TSP in the half integral case.
STOC
Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan
2019 J jnl
An Improved Approximation Algorithm for TSP in the Half Integral Case.
CoRR
Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan
2017 — conf
Symmetric-Key Broadcast Encryption: The Multi-sender Case.
CSCML
Cody Freitag, Jonathan Katz, Nathan Klein
2014 A conf
New features for duplicate bug detection.
MSR
Nathan Klein, Christopher S. Corley, Nicholas A. Kraft
2008 Misc conf
Feasibility study for replacing the MK19 automatic grenade launching system.
WSC
Kyle Hurst, Nathan Klein, Mario Feliciano, Steven Warner, Scott Crino