论文标题
$ S-T $ PATH TSP的正规率上的上限略有改进
Slightly Improved Upper Bound on the Integrality Ratio for the $s-t$ Path TSP
论文作者
论文摘要
在本文中，我们研究了公制$ s-t $路径TSP标准LP松弛的完整性比率。我们对用于分析Traub和Vygen的辅助函数做出了近乎理想的选择，该辅助功能可在整数比例为1.5273的上限上提高上限。
In this paper we investigate the integrality ratio of the standard LP relaxation for the metric $s-t$ Path TSP. We make a near-optimal choice for an auxiliary function used in the analysis of Traub and Vygen which leads to an improved upper bound on the integrality ratio of 1.5273.
