メトリックTSPに対する巡回路（サブツアー）LPの整合性ギャップのより鋭い明示的上界

Karlin, Klein, and Oveis Gharan は、メトリックTSPに対して、ランダム化による $3/2$ より良い近似アルゴリズムを導入し [KKO21]、その後、サブツアー除去LPの整合性ギャップにおける対応する改善を確立した [KKO22]。その改善には、明示的な定数 $\varepsilon>1.00000\cdot10^{-36}$ が含まれる。Gurvits, Klein, and Leake はその後、認証された節約量（certified saving）を $2.18000\cdot10^{-34}$ まで改善した [GKL24]。さらに、任意の固定した $\varepsilon<\varepsilon_\star$ に対して、ランダム化による多項式時間の $(3/2-\varepsilon)$-近似を得る。ここで $\varepsilon_\star>2.05522\cdot10^{-30}$ である。したがって、サブツアー除去LPの整合性ギャップは高々 $3/2-\varepsilon_\star$ となる。

https://doi.org/10.20944/preprints202609.0140.v1