Maximum ATSP with Weights Zero and One via Half-Edges
作者： Katarzyna Paluch
DOI: 10.1007/978-3-319-28684-6_3
关键词:
摘要: We present a fast combinatorial 3 / 4-approximation algorithm for the maximum asymmetric TSP with weights zero and one. The approximation factor of this matches currently best one given by Blaser in 2004 based on linear programming. Our first computes size matching weight cycle cover without certain cycles length two but possibly half-edges - half-edge edge e is informally speaking half that contains endpoints e. Then from computed it extracts set paths, whose large enough to be able construct traveling salesman tour claimed guarantee.
arxiv.org
springer.com
sci-hub.st 参考文章(17)
S. Rao Kosaraju, Clifford Stein, James K. Park, Long Tours and Short Superstrings (Preliminary Version) foundations of computer science. pp. 166- 177 ,(1994)
Richard Schmied, Marek Karpinski, Improved inapproximability results for the shortest superstring and related problems computing the australasian theory symposium. pp. 27- 36 ,(2013)
Katarzyna E. Paluch, Better Approximation Algorithms for Maximum Asymmetric Traveling Salesman and Shortest Superstring. arXiv: Data Structures and Algorithms. ,(2014)
Markus Bläser, Bodo Manthey, Two Approximation Algorithms for 3-Cycle Covers Lecture Notes in Computer Science. pp. 40- 50 ,(2002) , 10.1007/3-540-45753-4_6
Markus Bläser, A 3/4-Approximation Algorithm for Maximum ATSP with Weights Zero and One Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. ,vol. 3122, pp. 61- 71 ,(2004) , 10.1007/978-3-540-27821-4_6
Markus Bläser, Bodo Siebert, None, Computing Cycle Covers without Short Cycles european symposium on algorithms. pp. 368- 379 ,(2001) , 10.1007/3-540-44676-1_31
Sundar Vishwanathan, An approximation algorithm for the asymmetric travelling salesman problem with distances one and two Information Processing Letters. ,vol. 44, pp. 297- 302 ,(1992) , 10.1016/0020-0190(92)90103-3
Markus Bläser, An 8/13-approximation algorithm for the asymmetric maximum TSP Journal of Algorithms. ,vol. 50, pp. 23- 48 ,(2004) , 10.1016/S0196-6774(03)00112-3
Moshe Lewenstein, Maxim Sviridenko, A 5/8 Approximation Algorithm for the Maximum Asymmetric TSP SIAM Journal on Discrete Mathematics. ,vol. 17, pp. 237- 248 ,(2004) , 10.1137/S0895480102402861
Aleksander Mądry, Katarzyna Paluch, Marcin Mucha, A 7/9 - Approximation Algorithm for the Maximum Traveling Salesman Problem international workshop and international workshop on approximation randomization and combinatorial optimization algorithms and techniques. ,vol. 5687, pp. 298- 311 ,(2009) , 10.1007/978-3-642-03685-9_23