论文标题
圆圈不平等：TSP的新的，基于循环的刻面定义不平等
The Circlet Inequalities: A New, Circulant-Based Facet-Defining Inequality for the TSP
论文作者
论文摘要
对称旅行推销员问题（TSP）Polytope的方面定义不平等在多面体TSP研究和最先进的TSP求解器中都起着重要作用。在本文中，我们介绍了一类新的方面定义不等式，即\ emph {cicklet nocealities}。这些不等式首先是在研究循环TSP时在Gutekunst和Williamson \ cite {gut19b}中的猜测，它们在多面体TSP研究与汉密尔顿周期的数量理论研究之间提供了一座桥梁，这些循环是由2017年的Marco buratti造成的一位循环的循环均等的同一循环均等。我们的主要证明利用了这种对称性来证明圆圈不平等的有效性。然后，我们证明了小路的不等式是定义的，并在goemans \ cite {goe95b}之后计算其力量；它们达到了与NADDEF和Rinaldi \ cite {NAD92}的类似循环冠不平等的最差强度，但通常更强。
Facet-defining inequalities of the symmetric Traveling Salesman Problem (TSP) polytope play a prominent role in both polyhedral TSP research and state-of-the-art TSP solvers. In this paper, we introduce a new class of facet-defining inequalities, the \emph{circlet inequalities}. These inequalities were first conjectured in Gutekunst and Williamson \cite{Gut19b} when studying Circulant TSP, and they provide a bridge between polyhedral TSP research and number-theoretic investigations of Hamiltonian cycles stemming from a conjecture due to Marco Buratti in 2017. The circlet inequalities exhibit circulant symmetry by placing the same weight on all edges of a given length; our main proof exploits this symmetry to prove the validity of the circlet inequalities. We then show that the circlet inequalities are facet-defining and compute their strength following Goemans \cite{Goe95b}; they achieve the same worst-case strength as the similarly circulant crown inequalities of Naddef and Rinaldi \cite{Nad92}, but are generally stronger.
