Feasibility study for replacing the MK19 automatic grenade launching system. - Kyle Hurst; Nathan Klein; Mario Feliciano; Steven Warner; Scott Crino (WSC, 2008)

New features for duplicate bug detection. - Nathan Klein; Christopher S. Corley; Nicholas A. Kraft (MSR, 2014)

Symmetric-Key Broadcast Encryption: The Multi-sender Case. - Cody Freitag; Jonathan Katz; Nathan Klein (CSCML, 2017)

An improved approximation algorithm for TSP in the half integral case. - Anna R. Karlin; Nathan Klein; Shayan Oveis Gharan (STOC, 2020)

A (slightly) improved approximation algorithm for metric TSP. - Anna R. Karlin; Nathan Klein; Shayan Oveis Gharan (STOC, 2021)

An Improved Approximation Algorithm for the Minimum k-Edge Connected Multi-Subgraph Problem. - Anna R. Karlin; Nathan Klein; Shayan Oveis Gharan; Xinzhi Zhang 002 (CoRR, 2021)

A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP. - Anna R. Karlin; Nathan Klein; Shayan Oveis Gharan (FOCS, 2022)

An improved approximation algorithm for the minimum k-edge connected multi-subgraph problem. - Anna R. Karlin; Nathan Klein; Shayan Oveis Gharan; Xinzhi Zhang 002 (STOC, 2022)

A (Slightly) Improved Deterministic Approximation Algorithm for Metric TSP. - Anna R. Karlin; Nathan Klein; Shayan Oveis Gharan (CoRR, 2022)

Thin Trees for Laminar Families. - Nathan Klein; Neil Olver (FOCS, 2023)

Matroid Partition Property and the Secretary Problem. - Dorna Abdolazimi; Anna R. Karlin; Nathan Klein; Shayan Oveis Gharan (ITCS, 2023)

A 4/3-Approximation Algorithm for Half-Integral Cycle Cut Instances of the TSP. - Billy Jin; Nathan Klein; David P. Williamson (IPCO, 2023)

A Deterministic Better-than-3/2 Approximation Algorithm for Metric TSP. - Anna R. Karlin; Nathan Klein; Shayan Oveis Gharan (IPCO, 2023)

Ghost Value Augmentation for k-ECSS and k-ECSM. - D. Ellis Hershkowitz; Nathan Klein; Rico Zenklusen (CoRR, 2023)

From Trees to Polynomials and Back Again: New Capacity Bounds with Applications to TSP. - Leonid Gurvits; Nathan Klein; Jonathan Leake (ICALP, 2024)

A Better-Than-1.6-Approximation for Prize-Collecting TSP. - Jannis Blauth; Nathan Klein; Martin Nägele (IPCO, 2024)

A Lower Bound for the Max Entropy Algorithm for TSP. - Billy Jin; Nathan Klein; David P. Williamson (IPCO, 2024)

Ghost Value Augmentation for k-Edge-Connectivity. - D. Ellis Hershkowitz; Nathan Klein; Rico Zenklusen (STOC, 2024)

Finding Structure in Entropy: Improved Approximation Algorithms for TSP and other Graph Problems - Nathan Klein (2024)

A Randomized Rounding Approach for DAG Edge Deletion. - Sina Kalantarzadeh; Nathan Klein; Victor Reis (APPROX/RANDOM, 2025)

Dual Charging for Half-Integral TSP. - Nathan Klein; Mehrshad Taziki (APPROX/RANDOM, 2025)

A $ frac{4}{3}$-approximation algorithm for half-integral cycle cut instances of the TSP. - Billy Jin; Nathan Klein; David P. Williamson (Math. Program., 2025)