In this paper, we give a simple polynomial-time reduction of {L(p)-Labeling} on graphs with a small diameter to {Metric (Path) TSP}, which enables us to use numerous results on {(Metric) TSP}. On the practical side, we can utilize various high-performance heuristics for TSP, such as Concordo and LKH, to solve our problem. On the theoretical side, we can see that the problem for any p under this framework is 1.5-approximable, and it can be solved by the Held-Karp algorithm in O(2^n n^2) time, where n is the number of vertices, and so on.
翻译：在本文中,我们给小直径图上的 {Metric (Path) TSP} 简单多光度时间缩减 {L(p)-Labeling} {Metric (Path) TSP}, 这使我们能够在{(Metric) TSP} 上使用许多结果。 在实际方面, 我们可以用各种高性能的超常时间来帮助TSP解决我们的问题。 在理论方面, 我们可以看到这个框架下的任何 p 的问题都是1.5 相当的, 并且可以通过O( 2<unk> n n<unk> 2) 时间的 ODelt-Karp 算法来解决, 在那里, 圆顶数是n, 等等。</s>
相关内容
微信扫码咨询专知VIP会员