Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps

References

• [1] Anstreicher KM (2000) Eigenvalue bounds vs. semidefinite relaxations for the quadratic assignment problem. SIAM J. Optim. 11(1):254–265.Crossref, Google Scholar
• [2] Burer S, Vandenbussche D (2006) Solving lift-and-project relaxations of binary integer programs. SIAM J. Optim. 16(3):726–750.Crossref, Google Scholar
• [3] Christofides N (1976) Worst-case analysis of a new heuristic for the travelling salesman problem . Technical Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, PA.Google Scholar
• [4] Cunningham WH (1986) On Bounds for the Metric TSP (School of Mathematics and Statistics, Carleton University, Ottawa, Canada).Google Scholar
• [5] Cvetković D, Čangalović M, Kovačević-Vujčić V (1999) Semidefinite programming methods for the symmetric traveling salesman problem. Cornuéjols G, Burkard RE, Woeginger GJ, eds. Proc. Integer Programming and Combinatorial Optimization, 7th Internat. IPCO Conf., Lecture Notes in Computer Science, vol. 1610 (Springer, Berlin), 126–136.Google Scholar
• [6] Dantzig G, Fulkerson R, Johnson S (1954) Solution of a large-scale traveling-salesman problem. J. Oper. Res. Soc. Amer. 2(4):393–410.Link, Google Scholar
• [7] de Klerk E, Sotirov R (2010) Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem. Math. Programming 122(2):225.Crossref, Google Scholar
• [8] de Klerk E, Sotirov R (2012) Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry. Math. Programming 133(1):75–91.Crossref, Google Scholar
• [9] de Klerk E, De Oliveira Filho F, Pasechnik D (2012) Relaxations of combinatorial problems via association schemes. Anjos MF, Lasserre JB, eds. Handbook on Semidefinite, Conic and Polynomial Optimization, International Series in Operations Research & Management Science, vol. 166 (Springer, New York), 171–199.Crossref, Google Scholar
• [10] de Klerk E, Pasechnik DV, Sotirov R (2008) On semidefinite programming relaxations of the traveling salesman problem. SIAM J. Optim. 19(4):1559–1573.Crossref, Google Scholar
• [11] Goemans M, Rendl F (2000) Combinatorial optimization. Wolkowicz H, Saigal R, Vandenberghe L, eds. Handbook of Semidefinite Programming: Theory, Algorithms, and Applications (Springer, New York), 343–360.Crossref, Google Scholar
• [12] Goemans MX (1995) Worst-case comparison of valid inequalities for the TSP. Math. Programming 69:335–349.Crossref, Google Scholar
• [13] Gray RM (2006) Toeplitz and circulant matrices: A review. Foundations Trends Comm. Inform. Theory 2(3):155–239.Google Scholar
• [14] Gutekunst SC, Williamson DP (2018) The unbounded integrality gap of a semidefinite relaxation of the traveling salesman problem. SIAM J. Optim. 28(3):2073–2096.Crossref, Google Scholar
• [15] Hadley SW, Rendl F, Wolkowicz H (1992) A new lower bound via projection for the quadratic assignment problem. Math. Oper. Res. 17(3):727–739.Link, Google Scholar
• [16] Held M, Karp RM (1970) The traveling-salesman problem and minimum spanning trees. Oper. Res. 18(6):1138–1162.Link, Google Scholar
• [17] Horn RA, Johnson CR (1991) Topics in Matrix Analysis (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [18] Jeffrey A, Dai H-H (2008) Handbook of Mathematical Formulas and Integrals, 4th ed. (Academic Press, New York).Google Scholar
• [19] Karpinski M, Lampis M, Schmied R (2015) New inapproximability bounds for TSP. J. Comput. System Sci. 81(8):1665–1677.Crossref, Google Scholar
• [20] Koopmans TC, Beckmann M (1957) Assignment problems and the location of economic activities. Econometrica 25(1):53–76.Crossref, Google Scholar
• [21] Lasserre JB (2001) An explicit exact SDP relaxation for nonlinear 0-1 programs. Aardal K, Gerards B, eds. Proc. 8th Internat. IPCO Conf., Lecture Notes in Computer Science, vol. 2081 (Springer, Berlin), 293–303.Google Scholar
• [22] Lovász L, Schrijver A (1991) Cones of matrices and set-functions and 0–1 optimization. SIAM J. Optim. 1(2):166–190.Crossref, Google Scholar
• [23] Povh J, Rendl F (2009) Copositive and semidefinite relaxations of the quadratic assignment problem. Discrete Optim. 6(3):231–241.Crossref, Google Scholar
• [24] Serdyukov A (1978) On some extremal walks in graphs. Upravlyaemye Sistemy 17:76–79.Google Scholar
• [25] Sherali HD, Adams WP (1990) A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discrete Math. 3(3):411–430.Crossref, Google Scholar
• [26] Shmoys DB, Williamson DP (1990) Analyzing the Held-Karp TSP bound: A monotonicity property with application. Inform. Processing Lett. 35(6):281–285.Crossref, Google Scholar
• [27] Sotirov R (2012) SDP relaxations for some combinatorial optimization problems. Anjos MF, Lasserre JB, eds. Handbook on Semidefinite, Conic and Polynomial Optimization (Springer, New York), 795–819.Crossref, Google Scholar
• [28] Williamson DP, Shmoys DB (2011) The Design of Approximation Algorithms (Cambridge University Press, New York).Crossref, Google Scholar
• [29] Wolsey LA (1980) Heuristic analysis, linear programming and branch and bound. Rayward-Smith VJ, ed. Combinatorial Optimization II (Springer, Berlin), 121–134.Crossref, Google Scholar
• [30] Zhao Q, Karisch SE, Rendl F, Wolkowicz H (1998) Semidefinite programming relaxations for the quadratic assignment problem. J. Combinatorial Optim. 2(1):71–109.Crossref, Google Scholar