References-Update

1

S. Arora. Polynomial Time Approximation Schemes for Euclidean TSP and other Geometric Problems, Journal of the ACM, 45(5):753-782, 1998.

2

A. Asadpour, M. Goemans, A. Madry, S. Gharan, A. Saberi. An O(log n / log log n)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem, Proc. 21st SODA, 379-389, 2010.

3

P. Berman, M. Karpinski. 8/7-Approximation Algorithm for (1-2)-TSP, Proc. 17th SODA, 641-648, 2006.

4

M. Bläser. A 3/4-Approximation Algorithm for Maximum ATSP with Weights Zero and One, Proc. 8th APPROX-RANDOM, LNCS 3122:61-71, 2004.

5

S. Boyd, R. Sitters, S. van der Ster, L. Stougie. The Traveling Salesman Problem on Cubic and Subcubic Graphs, CoRR arXiv:abs/1107.1052, also appeared in Proc. 15th IPCO, LNCS 6655:65-77, 2011.

6

N. Christofides. Worst-case Analysis of a New Heuristic for the Travelling Salesman Problem, Technical Report CS-93-13. Carnegie Mellon University, 1976. (See also on Wikipedia.)

7

B. Csaba, M. Karpinski, P. Krysta. Approximability of Dense and Sparse Instances of Minimum 2-Connectivity, TSP and Path Problems, Proc. of the 13th Annual ACM-SIAM Symposium on Discrete Algorithmics, 74-83, 2002.

8

A. Golovnev. Approximation Algorithms for Metric TSP, Stackexchange.com, URL: http://cstheory.stackexchange.com/questions/9241/approximation-algorithms-for-metric-tsp

9

M. Karpinski, M. Lampis, R. Schmied. New Inapproximability Bounds for TSP, CoRR arXiv:abs/1303.6437, 2013; also appeared in Proc. 24th ISAAC, 568-578, 2013; to appear in J. Computer and System Sciences.

10

M. Karpinski, R. Schmied. Approximation Hardness of Graphic TSP on Cubic Graphs, CoRR arXiv:abs/1304.6800, 2013; journal version: RAIRO Operations Research 49 (2015), pages 651-668.

11

M. Karpinski, R. Schmied. On Approximation Lower Bounds with Bounded Metrics, CoRR arXiv:abs/1201.5821, 2012.

12

J. Mitchell. Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems, SIAM Journal on Computing, 28(4):1298-1309, 1999.

13

T. Mömke, O. Svensson. Approximating Graphic TSP by Matchings, CoRR arXiv:abs/1104.3090, also appeared in 52nd Annual Symposium on Foundations of Computer Science, 560-569, 2011.

14

A. Sebö, J. Vygen. Shorter Tours by Nicer Ears, CoRR arXiv:abs/1201.1870, 2012; To appear in Combinatorica.

15

L. Trevisan. When Hamming Meets Euclid: The Approximability of Geometric TSP and Steiner Tree, SIAM Journal on Computing, 30(2):475-485, 2000.