A lower bound for the max entropy algorithm for TSP

Abstract 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}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mfrac> <mml:mn>4</mml:mn> <mml:mn>3</mml:mn> </mml:mfrac> </mml:math> . For 40 years, the best known upper bound was 1.5, due to Wolsey [1]. Recently, Karlin, Klein, and Oveis Gharan [2] showed that the max entropy algorithm for the TSP gives an improved bound of $$1.5 - 10^{-36}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>1.5</mml:mn> <mml:mo>-</mml:mo> <mml:msup> <mml:mn>10</mml:mn> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>36</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> . In this paper, we show that the approximation ratio of the max entropy algorithm is at least 1.375, even for graph 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.