A lower bound for the max entropy algorithm for TSP

• 成果类型: Article
• 署名作者: Jin, Billy; Klein, Nathan; Williamson, David P.
• 署名单位: Purdue University System; Purdue University; Boston University; Cornell University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-025-02289-y
• 发表日期: 2026-03
• 页码: 425-447
• 关键词: traveling salesman problem; tsp; approximation algorithm; Lower bound; Graph algorithm; Max entropy; Subtour LP; Integrality gap

摘要

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 43\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{4}{3}$$\end{document}. 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\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1.5 - 10<^>{-36}$$\end{document}. 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.