Arrow Research search

Author name cluster

Nathan Klein

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers
1 author row

Possible papers

6

STOC Conference 2024 Conference Paper

Ghost Value Augmentation for k-Edge-Connectivity

  • D. Ellis Hershkowitz
  • Nathan Klein
  • Rico Zenklusen

We give a poly-time algorithm for the k -edge-connected spanning subgraph ( k -ECSS) problem that returns a solution of cost no greater than the cheapest ( k +10)-ECSS on the same graph. Our approach enhances the iterative relaxation framework with a new ingredient, which we call ghost values, that allows for high sparsity in intermediate problems. Our guarantees improve upon the best-known approximation factor of 2 for k -ECSS whenever the optimal value of ( k +10)-ECSS is close to that of k -ECSS. This is a property that holds for the closely related problem k -edge-connected spanning multi-subgraph ( k -ECSM), which is identical to k -ECSS except edges can be selected multiple times at the same cost. As a consequence, we obtain a 1+ O (1/ k )-approximation algorithm for k -ECSM, which resolves a conjecture of Pritchard and improves upon a recent 1+ O (1/√ k )-approximation algorithm of Karlin, Klein, Oveis Gharan, and Zhang. Moreover, we present a matching lower bound for k -ECSM, showing that our approximation ratio is tight up to the constant factor in O (1/ k ), unless P=NP.

Details

FOCS Conference 2023 Conference Paper

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 family is crossed. This generalizes the well-studied degree-bounded spanning tree problem, as well as a previously studied setting where a chain of cuts is given. We give the first constant-factor approximation algorithm; in particular we show how to obtain a multiplicative violation of the crossing bounds of less than 22 while losing less than a factor of 5 in terms of cost. Our result compares to the natural $L P$ relaxation. As a consequence, our results show that given a k-edge-connected graph and a laminar family $\mathcal{L} \subseteq 2^{V}$ of cuts, there exists a spanning tree which contains only an $O(1 / k)$ fraction of the edges across every cut in $\mathcal{L}$. This can be viewed as progress towards the Thin Tree Conjecture, which (in a strong form) states that this guarantee can be obtained for all cuts simultaneously.

Details

FOCS Conference 2022 Conference Paper

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

  • Anna R. Karlin
  • Nathan Klein
  • Shayan Oveis Gharan

In this extended abstract, we show that for some $\epsilon>10^{-36}$ and any metric TSP instance, the max entropy algorithm studied by [1] returns a solution of expected cost at most $\frac{3}{2}-\epsilon$ times the cost of the optimal solution to the subtour elimination LP. This implies that the integrality gap of the subtour LP is at most $\frac{3}{2}-\epsilon$. This analysis also shows that there is a randomized $\frac{3}{2}-\epsilon$ approximation for the 2-edge-connected multi-subgraph problem, improving upon Christofides’ algorithm.

Details

STOC Conference 2020 Conference Paper

An improved approximation algorithm for TSP in the half integral case

  • Anna R. Karlin
  • Nathan Klein
  • Shayan Oveis Gharan

We design a 1.49993-approximation algorithm for the metric traveling salesperson problem (TSP) for instances in which an optimal solution to the subtour linear programming relaxation is half-integral. These instances received significant attention over the last decade due to a conjecture of Schalekamp, Williamson and van Zuylen stating that half-integral LP solutions have the largest integrality gap over all fractional solutions. So, if the conjecture of Schalekamp et al. holds true, our result shows that the integrality gap of the subtour polytope is bounded away from 3/2.

Details
v2026.09.13