3 citations · 5 across the 7 of their papers we have counts for
9 papers
A Better-Than-1.6-Approximation for Prize-Collecting TSP
Jannis Blauth, Nathan Klein, Martin Nägele
Prize-Collecting TSP is a variant of the traveling salesperson problem where one may drop vertices from the tour at the cost of vertex-dependent penalties. The quality of a solutio…
Thin trees for laminar families
Nathan Klein, Neil Olver
In the laminar-constrained spanning tree problem, the goal is to find a minimum-cost spanning tree which respects upper bounds on the number of times each cut in a given laminar fa…
A (Slightly) Improved Deterministic Approximation Algorithm for Metric TSP
Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan
We show that the max entropy algorithm can be derandomized (with respect to a particular objective function) to give a deterministic approximation algorithm for metric TSP…
A 4/3-Approximation Algorithm for Half-Integral Cycle Cut Instances of the TSP
Billy Jin, Nathan Klein, David P. Williamson
A long-standing conjecture for the traveling salesman problem (TSP) states that the integrality gap of the standard linear programming relaxation of the TSP is at most 4/3. Despite…
Matroid Partition Property and the Secretary Problem
Dorna Abdolazimi, Anna R. Karlin, Nathan Klein +1
A matroid on a set of elements has the -partition property, for some , if it is possible to (randomly) construct a partition matroid on (a s…
A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP
Anna Karlin, Nathan Klein, Shayan Oveis Gharan
We show that for some and any metric TSP instance, the max entropy algorithm returns a solution of expected cost at most times the cost of the optimal…
An Improved Approximation Algorithm for the Minimum -Edge Connected Multi-Subgraph Problem
Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan +1
We give a randomized -approximation algorithm for the minimum -edge connected spanning multi-subgraph problem, -ECSM.
A (Slightly) Improved Approximation Algorithm for Metric TSP
Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan
For some we give a randomized approximation algorithm for metric TSP.
An Improved Approximation Algorithm for TSP in the Half Integral Case
Anna Karlin, Nathan Klein, Shayan Oveis Gharan
We design a -approximation algorithm for the metric traveling salesperson problem (TSP) for instances in which an optimal solution to the subtour linear programming relaxa…