Approximation hardness of graphic TSP on cubic graphs
作者： Marek Karpinski , Richard Schmied
DOI: 10.1051/RO/2014062
关键词:
摘要: We prove explicit approximation hardness results for the Graphic TSP on cubic and subcubic graphs as well new inapproximability bounds corresponding instances of (1,2)-TSP. The result is first known that problem. proof technique in this paper uses modular constructions simulating gadgets restricted instances. used could be also independent interest.
harvard.edu
sci-hub.se 参考文章(21)
Richard Schmied, Marek Karpinski, Improved inapproximability results for the shortest superstring and related problems computing the australasian theory symposium. pp. 27- 36 ,(2013)
Piotr Berman, Marek Karpinski, On Some Tighter Inapproximability Results (Extended Abstract) international colloquium on automata languages and programming. pp. 200- 209 ,(1999) , 10.1007/3-540-48523-6_17
Piotr Berman, Marek Karpinski, On Some Tighter Inapproximability Results international colloquium on automata languages and programming. pp. 200- 209 ,(1998)
Michael Lampis, Richard Schmied, Marek Karpinski, New Inapproximability Bounds for TSP arXiv: Computational Complexity. ,(2013)
Richard Schmied, Marek Karpinski, On Approximation Lower Bounds for TSP with Bounded Metrics arXiv: Computational Complexity. ,(2012)
José R. Correa, Omar Larré, José A. Soto, TSP Tours in Cubic Graphs: Beyond 4/3 Algorithms – ESA 2012. pp. 790- 801 ,(2012) , 10.1007/978-3-642-33090-2_68
Piotr Berman, Marek Karpinski, 8/7-approximation algorithm for (1,2)-TSP symposium on discrete algorithms. pp. 641- 648 ,(2006) , 10.5555/1109557.1109627
Marcin Mucha, $\frac{13}{9}$-Approximation for Graphic TSP Theory of Computing Systems \/ Mathematical Systems Theory. ,vol. 55, pp. 640- 657 ,(2014) , 10.1007/S00224-012-9439-7
David Gamarnik, Moshe Lewenstein, Maxim Sviridenko, An improved upper bound for the TSP in cubic 3-edge-connected graphs Operations Research Letters. ,vol. 33, pp. 467- 474 ,(2005) , 10.1016/J.ORL.2004.09.005
Johan Håstad, Some optimal inapproximability results Journal of the ACM. ,vol. 48, pp. 798- 859 ,(2001) , 10.1145/502090.502098