On Approximation Lower Bounds for TSP with Bounded Metrics
作者： Richard Schmied , Marek Karpinski
DOI:
关键词: Upper and lower bounds 、 Mathematics 、 Bounded function 、 Discrete mathematics 、 Combinatorics 、 Metric (mathematics)
摘要: We develop a new method for proving explicit approximation lower bounds TSP problems with bounded metrics improving on the best up to now known bounds. They almost match unbounded metric problems. In particular, we prove bound equal 4.
arxiv.org
harvard.edu参考文章(13)
Piotr Berman, Marek Karpinski, Improved Approximation Lower Bounds on Small Occurrence Optimization Electronic Colloquium on Computational Complexity. ,vol. 10, ,(2003)
Piotr Berman, Marek Karpinski, On Some Tighter Inapproximability Results international colloquium on automata languages and programming. pp. 200- 209 ,(1998)
Michael Lampis, Improved Inapproximability for TSP Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. ,vol. 10, pp. 243- 253 ,(2012) , 10.1007/978-3-642-32512-0_21
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
Richard Schmied, Marek Karpinski, Improved Lower Bounds for the Shortest Superstring and Related Problems arXiv: Computational Complexity. ,(2011)
Johan Håstad, Some optimal inapproximability results Journal of the ACM. ,vol. 48, pp. 798- 859 ,(2001) , 10.1145/502090.502098
Luca Trevisan, When Hamming Meets Euclid: The Approximability of Geometric TSP and Steiner Tree SIAM Journal on Computing. ,vol. 30, pp. 475- 485 ,(2000) , 10.1137/S0097539799352735
Lars Engebretsen, Marek Karpinski, TSP with bounded metrics Journal of Computer and System Sciences. ,vol. 72, pp. 509- 546 ,(2006) , 10.1016/J.JCSS.2005.12.001
Christos H. Papadimitriou*, Santosh Vempala†, On The Approximability Of The Traveling Salesman Problem Combinatorica. ,vol. 26, pp. 101- 120 ,(2006) , 10.1007/S00493-006-0008-Z
Michel X. Goemans, Shayan Oveis Gharan, Aleksander Mądry, Arash Asadpour, Amin Saberi, An O(log n/ log log n)-approximation algorithm for the asymmetric traveling salesman problem symposium on discrete algorithms. pp. 379- 389 ,(2010) , 10.5555/1873601.1873633