Nathan Klein

Nathan Klein, Neil Olver, Zi Song Yeoh

The strong thin tree conjecture states that every $k$-edge-connected graph $G$ contains an $O(1/k)$-thin spanning tree, meaning a spanning tree which contains at most an $O(1/k)$ fraction of the edges across each cut in $G$. This conjecture is still open despite significant effort; the best current result by Anari and Oveis Gharan shows the existence of an $O(\text{polyloglog}(n)/k)$-thin tree. In this work, we demonstrate that the conjecture is true if one only requires thinness for the set of $η$-near minimum cuts of the graph for $η= 1/40$, in other words, for the set of cuts with fewer than $(1+1/40)k$ edges. Our approach constructs such a tree in polynomial time. To show this, we utilize the structure of near minimum cuts, and in particular the polygon representation of Benczúr and Goemans, to reduce to the previously solved problem of finding a spanning tree that is $O(1/k)$-thin for all sets in a laminar family.

Billy Jin, Nathan Klein, David P. Williamson

One of the most famous conjectures in combinatorial optimization is the four-thirds conjecture, which states that the integrality gap of the Subtour LP relaxation of the TSP is equal to $\frac{4}{3}$. For 40 years, the best known upper bound was $1.5$, due to Wolsey. Recently, Karlin, Klein, and Oveis Gharan showed that the max entropy algorithm for the TSP gives an improved bound of $1.5 - 10^{-36}$. In this paper, we show that the maximum entropy algorithm is a $\frac{10}{7}$-approximation for half-integral cycle cut instances of the TSP. This class of instances contains examples which demonstrate the subtour LP has an integrality gap of at least $\frac{4}{3}$, as well as examples showing that the performance of the max entropy algorithm is no better than $\frac{11}{8}$. We note that in the authors recently gave an algorithm upper bounding the integrality gap of this class of instances by $\frac{4}{3}$, so this work does not (and could not) provide an improved bound on the integrality gap. However, since there is no reason to believe that the analysis of the maximum entropy algorithm on general instances is tight, our work provides hope (and potentially direction) for improved analysis on other instance classes.