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 4/3. For 40 years, the best known upper bound was 1.5. 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 approximation ratio of the max entropy algorithm is at least 1.375, even for graphic TSP. Thus the max entropy algorithm does not appear to be the algorithm that will ultimately resolve the four-thirds conjecture in the affirmative, should that be possible.

Our new book (with the same title as this talk) describes and advances the state of the art on approximation algorithms for the main variants of the traveling salesman problem. Here we present some new results from this book (including a better approximation ratio for the asymmetric TSP and its path version), outline the state of the art, and mention some important open problems.

We consider an unsplittable version of the minimum max-load multicommodity flow problem, where each demand must be routed along a single path. The objective is to minimize the maximum load on any edge in the network. In a seminal work, Schrijver, Seymour, and Winkler showed how to efficiently solve this problem on a cycle to within an additive term of $\tfrac{3}{2}W$ of the optimal value, where $W$ is the largest demand between any two nodes.
We extend their result to outerplanar graphs and provide an efficient algorithm for this problem that exceeds the optimal value by an additive term of no more than $O(W \log k)$, where $k$ is the number of faces in the graph. This implies an $O(\log k)$ approximation ratio.
We also extend this result to planar graphs with bounded treewidth and demands on the outer face, for which we also achieve an additive $O(W \log k)$ error term.

A long-standing conjecture for the traveling salesman problem (TSP) states that the integrality gap of the standard linear programming relaxation of the TSP (sometimes called the Subtour LP or the Held-Karp bound) is at most 4/3 for symmetric instances of the TSP obeying the triangle inequality. We consider the half-integral case, in which a feasible solution to the LP has solution values in {0, 1/2, 1}. Karlin, Klein, and Oveis Gharan, in a breakthrough result, were able to show that in the half-integral case, the integrality gap is at most 1.49993; Gupta et al. show a slight improvement of this result to 1.4983. Both of these papers consider a hierarchy of critical tight sets in the support graph of the LP solution, in which some of the sets correspond to `cycle cuts’ and the others to `degree cuts’. Here we show that if all the sets in the hierarchy correspond to cycle cuts, then we can find a distribution of tours whose expected cost is at most 4/3 times the value of the half-integral LP solution; sampling from the distribution gives us a randomized 4/3-approximation algorithm. We note that known bad cases for the integrality gap have a gap of 4/3 and have a half-integral LP solution in which all the critical tight sets in the hierarchy are cycle cuts; thus our result is tight. This is joint work with Nathan Klein and Billy Jin.