Nathan Klein

According to our database, Nathan Klein authored at least 17 papers between 2008 and 2023.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2023

From Trees to Polynomials and Back Again: New Capacity Bounds with Applications to TSP.

Leonid Gurvits, Nathan Klein, Jonathan Leake

Electron. Colloquium Comput. Complex., 2023

Ghost Value Augmentation for k-ECSS and k-ECSM.

D. Ellis Hershkowitz, Nathan Klein, Rico Zenklusen

CoRR, 2023

A Lower Bound for the Max Entropy Algorithm for TSP.

Billy Jin, Nathan Klein, David P. Williamson

CoRR, 2023

A Better-Than-1.6-Approximation for Prize-Collecting TSP.

Jannis Blauth, Nathan Klein, Martin Nägele

CoRR, 2023

A Deterministic Better-than-3/2 Approximation Algorithm for Metric TSP.

Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan

Proceedings of the Integer Programming and Combinatorial Optimization, 2023

A 4/3-Approximation Algorithm for Half-Integral Cycle Cut Instances of the TSP.

Billy Jin, Nathan Klein, David P. Williamson

Proceedings of the Integer Programming and Combinatorial Optimization, 2023

Matroid Partition Property and the Secretary Problem.

Dorna Abdolazimi, Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Thin Trees for Laminar Families.

Nathan Klein, Neil Olver

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

2022

A (Slightly) Improved Deterministic Approximation Algorithm for Metric TSP.

Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan

CoRR, 2022

An improved approximation algorithm for the minimum <i>k</i>-edge connected multi-subgraph problem.

Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan, Xinzhi Zhang

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP.

Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

An Improved Approximation Algorithm for the Minimum k-Edge Connected Multi-Subgraph Problem.

Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan, Xinzhi Zhang

CoRR, 2021

A (slightly) improved approximation algorithm for metric TSP.

Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

2020

An improved approximation algorithm for TSP in the half integral case.

Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

2017

Symmetric-Key Broadcast Encryption: The Multi-sender Case.

Cody Freitag, Jonathan Katz, Nathan Klein

Proceedings of the Cyber Security Cryptography and Machine Learning, 2017

2014

New features for duplicate bug detection.

Nathan Klein, Christopher S. Corley, Nicholas A. Kraft

Proceedings of the 11th Working Conference on Mining Software Repositories, 2014

2008

Feasibility study for replacing the MK19 automatic grenade launching system.

Kyle Hurst, Nathan Klein, Mario Feliciano, Steven Warner, Scott Crino

Proceedings of the 2008 Winter Simulation Conference, Global Gateway to Discovery, 2008