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