An 8/13-approximation algorithm for the asymmetric maximum TSP
作者： Markus Bläser
DOI: 10.1016/S0196-6774(03)00112-3
关键词:
摘要: We present a polynomial time approximation algorithm for the asymmetric maximum traveling salesperson problem that achieves performance ratio 8/13 (1 - 1/n). The running of our is O(n3).
elsevier.com
sci-hub.se 参考文章(17)
S. Rao Kosaraju, Clifford Stein, James K. Park, Long Tours and Short Superstrings (Preliminary Version) foundations of computer science. pp. 166- 177 ,(1994)
Joseph F. Traub, Algorithms and Complexity: New Directions and Recent Results Academic Press, Inc.. ,(1976)
Refael Hassin, Shlomi Rubinstein, A -approximation algorithm for metric Max TSP Information Processing Letters. ,vol. 81, pp. 247- 251 ,(2002) , 10.1016/S0020-0190(01)00234-4
Maxim Sviridenko, Moshe Lewenstein, Approximating asymmetric maximum TSP symposium on discrete algorithms. pp. 646- 654 ,(2003) , 10.5555/644108.644214
Santosh Vempala, Robert D. Carr, Towards a 4/3 approximation for the asymmetric traveling salesman problem symposium on discrete algorithms. pp. 116- 125 ,(2000) , 10.5555/338219.338242
Refael Hassin, Shlomi Rubinstein, Better approximations for max TSP Information Processing Letters. ,vol. 75, pp. 181- 186 ,(2000) , 10.1016/S0020-0190(00)00097-1
A. M. Frieze, G. Galbiati, F. Maffioli, On the worst‐case performance of some algorithms for the asymmetric traveling salesman problem Networks. ,vol. 12, pp. 23- 39 ,(1982) , 10.1002/NET.3230120103
Z. Sweedyk, \boldmath A $2\frac12$-Approximation Algorithm for Shortest Superstring SIAM Journal on Computing. ,vol. 29, pp. 954- 986 ,(1999) , 10.1137/S0097539796324661
Jonathan S. Turner, Approximation algorithms for the shortest common superstring problem Information & Computation. ,vol. 83, pp. 1- 20 ,(1989) , 10.1016/0890-5401(89)90044-8
Jorma Tarhio, Esko Ukkonen, A greedy approximation algorithm for constructing shortest common superstrings mathematical foundations of computer science. ,vol. 57, pp. 131- 145 ,(1988) , 10.1016/0304-3975(88)90167-3