论文标题
A（稍有）改进的公制TSP的确定性近似算法
A (Slightly) Improved Deterministic Approximation Algorithm for Metric TSP
论文作者
论文摘要
我们表明，最大熵算法可以被取代（相对于特定的目标函数），以给出确定性的$ 3/2-ε$ $近似算法，用于公制TSP的某些$ε> 10^{ - 36} $。 为了获得我们的结果，我们将条件期望的方法应用于先前工作中构建的目标函数，该方法用于证明该算法的预期成本最多为$ 3/2-ε$倍乘以子程度消除LP的最佳解决方案的成本。这项工作的证明涉及表明该目标函数的预期值可以在多项式时间（在算法执行的所有阶段）计算。
We show that the max entropy algorithm can be derandomized (with respect to a particular objective function) to give a deterministic $3/2-ε$ approximation algorithm for metric TSP for some $ε> 10^{-36}$. To obtain our result, we apply the method of conditional expectation to an objective function constructed in prior work which was used to certify that the expected cost of the algorithm is at most $3/2-ε$ times the cost of an optimal solution to the subtour elimination LP. The proof in this work involves showing that the expected value of this objective function can be computed in polynomial time (at all stages of the algorithm's execution).
