Improved Lower Bounds for the Universal and a priori TSP
Improved Lower Bounds for the Universal and a priori TSP
复制标题
改进通用和先验 TSP 的下限
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Gwen Spencer
中科院分区：
文献类型：
--
作者：
I. Gorodezky;Robert D. Kleinberg;D. Shmoys;Gwen Spencer
我们考虑两个部分信息推广的度量旅行商问题（TSP），其中的任务是产生一个总的排序的一个给定的度量空间，表现良好的一个子集的空间，这是不知道在事先。在通用TSP中，子集是逆选择的，而在先验TSP中，子集是概率选择的。自80年代中期以来，普遍的和先验的TSP都得到了研究，分别从Bartholdi & Platzman和Jaillet的工作开始。通过定义Ramanujan图上最短路径度量的竞争比，证明了一般TSP的竞争比Ω（log n）的一个下界，改进了Hajiaghayi，Kleinberg & Leighton的最佳界，即n × n网格上的竞争比Ω（n × 6log n/log log n）.此外，我们表明，对于一类大的组合优化问题，包括TSP，一个普遍的问题的界意味着匹配的约束上的近似比确定性算法实现相应的黑盒先验问题。因此，我们对普遍TSP的Ω（log n）的下界意味着对黑盒先验TSP的匹配下界。
We consider two partial-information generalizations of the metric traveling salesman problem (TSP) in which the task is to produce a total ordering of a given metric space that performs well for a subset of the space that is not known in advance. In the universal TSP, the subset is chosen adversarially, and in the a priori TSP it is chosen probabilistically. Both the universal and a priori TSP have been studied since the mid-80's, starting with the work of Bartholdi & Platzman and Jaillet, respectively. We prove a lower bound of Ω(log n) for the universal TSP by bounding the competitive ratio of shortest-path metrics on Ramanujan graphs, which improves on the previous best bound of Hajiaghayi, Kleinberg & Leighton, who showed that the competitive ratio of the n × n grid is Ω(√6log n/log log n). Furthermore, we show that for a large class of combinatorial optimization problems that includes TSP, a bound for the universal problem implies a matching bound on the approximation ratio achievable by deterministic algorithms for the corresponding black-box a priori problem. As a consequence, our lower bound of Ω(log n) for the universal TSP implies a matching lower bound for the black-box a priori TSP.