×

zbMATH — the first resource for mathematics

The unbounded integrality gap of a semidefinite relaxation of the traveling salesman problem. (English) Zbl 1402.90114

MSC:
90C22 Semidefinite programming
90C27 Combinatorial optimization
05C85 Graph algorithms (graph-theoretic aspects)
68W25 Approximation algorithms
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] S. Arora, Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems, J. ACM, 45 (1998), pp. 753–782. · Zbl 1064.90566
[2] K. K. Cheung, On Lovász–Schrijver lift-and-project procedures on the Dantzig–Fulkerson–Johnson relaxation of the TSP, SIAM J. Optim., 16 (2005), pp. 380–399. · Zbl 1122.90065
[3] E. Chlamtac and M. Tulsiani, Convex relaxations and integrality gaps, in Handbook on Semidefinite, Conic and Polynomial Optimization, Internat. Ser. Oper. Res. Management Sci. 166, M. F. Anjos and J. B. Lasserre, eds., Springer, New York, 2012, pp. 139–169. · Zbl 1334.90099
[4] N. Christofides, Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem, Technical report 388, Carnegie-Mellon University, Pittsburgh, PA, 1976.
[5] D. Cvetković, M. Čangalović, and V. Kovačević-Vujčić, Semidefinite programming methods for the symmetric traveling salesman problem, in IPCO 1999: Integer Programming and Combinatorial Optimization, Lecture Notes in Comput. Sci. 1610, G. Cornuéjols, R. E. Burkard, and G. J. Woeginger, eds., Springer, Berlin, 1999, pp. 126–136.
[6] G. Dantzig, R. Fulkerson, and S. Johnson, Solution of a large-scale traveling-salesman problem, J. Oper. Res. Soc. Amer., 2 (1954), pp. 393–410.
[7] E. de Klerk, F. de Oliveira Filho, and D. Pasechnik, Relaxations of combinatorial problems via association schemes, in Handbook on Semidefinite, Conic and Polynomial Optimization, Internat. Ser. Oper. Res. Management Sci. 166, M. F. Anjos and J. B. Lasserre, eds., Springer, New York, 2012, pp. 171–199. · Zbl 1334.90100
[8] E. de Klerk and C. Dobre, A comparison of lower bounds for the symmetric circulant traveling salesman problem, Discrete Appl. Math., 159 (2011), pp. 1815–1826. · Zbl 1228.90103
[9] E. de Klerk, D. V. Pasechnik, and R. Sotirov, On semidefinite programming relaxations of the traveling salesman problem, SIAM J. Optim., 19 (2008), pp. 1559–1573. · Zbl 1196.90094
[10] E. de Klerk and R. Sotirov, Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry, Math. Program., 133 (2012), pp. 75–91. · Zbl 1270.90045
[11] Z. Gao, On the metric \(s\)–\(t\) path traveling salesman problem, SIAM J. Discrete Math., 29 (2015), pp. 1133–1149. · Zbl 1331.68293
[12] S. O. Gharan, A. Saberi, and M. Singh, A randomized rounding approach to the traveling salesman problem, in Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, IEEE Press, Piscataway, NJ, 2011, pp. 550–559; available at . · Zbl 1292.68171
[13] M. Goemans and F. Rendl, Combinatorial optimization, in Handbook of Semidefinite Programming: Theory, Algorithms, and Applications, Internat. Ser. Oper. Res. Management Sci. 27, H. Wolkowicz, R. Saigal, and L. Vandenberghe, eds., Springer, New York, 2000, pp. 343–360. · Zbl 0957.90514
[14] M. X. Goemans and F. Rendl, Semidefinite programs and association schemes, Computing, 63 (1999), pp. 331–340. · Zbl 0956.90029
[15] M. X. Goemans and D. P. Williamson, A general approximation technique for constrained forest problems, SIAM J. Computing, 24 (1995), pp. 296–317. · Zbl 0834.68055
[16] R. M. Gray, Toeplitz and circulant matrices: A review, Found. Trends Commun. Inform. Theory, 2 (2006), pp. 155–239.
[17] M. Grötschel and M. W. Padberg, Polyhedral theory, in The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, E. L. Lawler, J. K. Lenstra, A. H. G. Rinnoy Kan, and D. B. Shmoys, eds., John Wiley & Sons, New York, 1985, pp. 251–306.
[18] S. C. Gutekunst and D. P. Williamson, The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem, preprint, , 2017. · Zbl 1402.90114
[19] M. Held and R. M. Karp, The traveling-salesman problem and minimum spanning trees, Oper. Res., 18 (1970), pp. 1138–1162. · Zbl 0226.90047
[20] R. A. Horn and C. R. Johnson, Topics in Matrix Analysis, Cambridge University Press, Cambridge, 1991. · Zbl 0729.15001
[21] A. Jeffrey and H.-H. Dai, Handbook of Mathematical Formulas and Integrals, 4th ed., Academic Press, New York, 2008. · Zbl 1139.00004
[22] M. Karpinski, M. Lampis, and R. Schmied, New inapproximability bounds for TSP, J. Comput. System Sci., 81 (2015), pp. 1665–1677. · Zbl 1328.68076
[23] J. B. Lasserre, An explicit exact SDP relaxation for nonlinear 0–1 programs, in IPCO 2001: Integer Programming and Combinatorial Optimization, Lecture Notes in Comput. Sci. 2081, K. Aardal and B. Gerards, eds., Springer, Berlin, 2001, pp. 293–303. · Zbl 1010.90515
[24] L. Lovász and A. Schrijver, Cones of matrices and set-functions and 0–1 optimization, SIAM J. Optim., 1 (1991), pp. 166–190. · Zbl 0754.90039
[25] J. S. B. Mitchell, Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, \(k\)-MST, and related problems, SIAM J. Comput., 28 (1999), pp. 1298–1309. · Zbl 0940.68062
[26] T. Mömke and O. Svensson, Removing and adding edges for the traveling salesman problem, J. ACM, 63 (2016), Article 2. · Zbl 1426.90219
[27] M. Mucha, 13/9-approximation for graphic TSP, Theory Comput. Syst., 55 (2014), pp. 640–657. · Zbl 1319.68255
[28] A. Sebö and J. Vygen, Shorter tours by nicer ears: 7/5-approximation for the graph-tsp, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs, Combinatorica, 34 (2014), pp. 597–629. · Zbl 1340.90201
[29] H. D. Sherali and W. P. Adams, A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems, SIAM J. Discrete Math., 3 (1990), pp. 411–430. · Zbl 0712.90050
[30] D. B. Shmoys and D. P. Williamson, Analyzing the Held–Karp TSP bound: A monotonicity property with application, Inform. Process. Lett., 35 (1990), pp. 281–285. · Zbl 0698.68050
[31] D. A. Spielman, Spectral graph theory and its applications, in Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, IEEE Press, Piscataway, NJ, 2007, pp. 29–38; available at .
[32] D. P. Williamson and D. B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, New York, 2011. · Zbl 1219.90004
[33] L. A. Wolsey, Heuristic analysis, linear programming and branch and bound, in Combinatorial Optimization II, V. J. Rayward-Smith, ed., Springer, Berlin, 1980, pp. 121–134. · Zbl 0442.90061
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.