Nathan Klein

Publication Activity (10 Years)

Years Active: 2008-2024
Publications (10 Years): 26

Top Topics

Travelling Salesman

Ant Colony Optimization

Integrality Gap

Monotonicity Property

Top Venues

Publications

Billy Jin, Nathan Klein, David P. Williamson
A Lower Bound for the Max Entropy Algorithm for TSP. IPCO (2024)
Leonid Gurvits, Nathan Klein, Jonathan Leake
From Trees to Polynomials and Back Again: New Capacity Bounds with Applications to TSP. ICALP (2024)
Jannis Blauth, Nathan Klein, Martin Nägele
A Better-Than-1.6-Approximation for Prize-Collecting TSP. IPCO (2024)
D. Ellis Hershkowitz, Nathan Klein, Rico Zenklusen
Ghost Value Augmentation for k-Edge-Connectivity. STOC (2024)
Dorna Abdolazimi, Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan
Matroid Partition Property and the Secretary Problem. ITCS (2023)
Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan
A Deterministic Better-than-3/2 Approximation Algorithm for Metric TSP. IPCO (2023)
Leonid Gurvits, Nathan Klein, Jonathan Leake
From Trees to Polynomials and Back Again: New Capacity Bounds with Applications to TSP. CoRR (2023)
Nathan Klein, Neil Olver
Thin Trees for Laminar Families. FOCS (2023)
Jannis Blauth, Nathan Klein, Martin Nägele
A Better-Than-1.6-Approximation for Prize-Collecting TSP. CoRR (2023)
Billy Jin, Nathan Klein, David P. Williamson
A Lower Bound for the Max Entropy Algorithm for TSP. CoRR (2023)
D. Ellis Hershkowitz, Nathan Klein, Rico Zenklusen
Ghost Value Augmentation for k-ECSS and k-ECSM. CoRR (2023)
Nathan Klein, Neil Olver
Thin trees for laminar families. CoRR (2023)
Leonid Gurvits, Nathan Klein, Jonathan Leake
From Trees to Polynomials and Back Again: New Capacity Bounds with Applications to TSP. Electron. Colloquium Comput. Complex. (2023)
Billy Jin, Nathan Klein, David P. Williamson
A 4/3-Approximation Algorithm for Half-Integral Cycle Cut Instances of the TSP. IPCO (2023)
Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan, Xinzhi Zhang
-edge connected multi-subgraph problem. STOC (2022)
Billy Jin, Nathan Klein, David P. Williamson
A 4/3-Approximation Algorithm for Half-Integral Cycle Cut Instances of the TSP. CoRR (2022)
Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan
A (Slightly) Improved Deterministic Approximation Algorithm for Metric TSP. CoRR (2022)
Anna Karlin, Nathan Klein, Shayan Oveis Gharan
A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP. FOCS (2022)
Dorna Abdolazimi, Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan
Matroid Partition Property and the Secretary Problem. CoRR (2021)
Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan, Xinzhi Zhang
An Improved Approximation Algorithm for the Minimum k-Edge Connected Multi-Subgraph Problem. CoRR (2021)
Anna Karlin, Nathan Klein, Shayan Oveis Gharan
A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP. CoRR (2021)
Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan
A (slightly) improved approximation algorithm for metric TSP. STOC (2021)
Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan
An improved approximation algorithm for TSP in the half integral case. STOC (2020)
Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan
A (Slightly) Improved Approximation Algorithm for Metric TSP. CoRR (2020)
Anna Karlin, Nathan Klein, Shayan Oveis Gharan
An Improved Approximation Algorithm for TSP in the Half Integral Case. CoRR (2019)
Cody Freitag, Jonathan Katz, Nathan Klein
Symmetric-Key Broadcast Encryption: The Multi-sender Case. CSCML (2017)
Nathan Klein, Christopher S. Corley, Nicholas A. Kraft
New features for duplicate bug detection. MSR (2014)
Kyle Hurst, Nathan Klein, Mario Feliciano, Steven Warner, Scott Crino
Feasibility study for replacing the MK19 automatic grenade launching system. WSC (2008)