The Circlet Inequalities: A New, Circulant-Based, Facet-Defining Inequality for the TSP

References

• [1] Applegate DL, Bixby R, Chvatal V, Cook W (2006) Concorde TSP solver.Google Scholar
• [2] Applegate DL, Bixby RE, Chvatál V, Cook WJ (2006) The Traveling Salesman Problem: A Computational Study (Princeton University Press, Princeton, NJ).Google Scholar
• [3] Applegate DL, Bixby RE, Chvátal V, Cook W, Espinoza DG, Goycoolea M, Helsgaun K (2009) Certification of an optimal TSP tour through 85,900 cities. Oper. Res. Lett. 37(1):11–15.Crossref, Google Scholar
• [4] Boyd SC, Cunningham WH (1991) Small traveling salesman polytopes. Math. Oper. Res. 16(2):259–271.Link, Google Scholar
• [5] Buratti M, Merola F (2013) Dihedral Hamiltonian cycle systems of the cocktail party graph. J. Combinatorial Designs 21(1):1–23.Crossref, Google Scholar
• [6] Burkard R, Sandholzer W (1991) Efficiently solvable special cases of bottleneck traveling salesman problems. Discrete Appl. Math. 32(1):61–76.Crossref, Google Scholar
• [7] Chvátal V (1973) Edmonds polytopes and weakly Hamiltonian graphs. Math. Programming 5(1):29–40.Crossref, Google Scholar
• [8] Codenotti B, Gerace I, Vigna S (1998) Hardness results and spectral techniques for combinatorial problems on circulant graphs. Linear Algebra Appl. 285(1):123–142.Crossref, Google Scholar
• [9] Cornuéjols G, Fonlupt J, Naddef D (1985) The traveling salesman problem on a graph and some related integer polyhedra. Math. Programming 33(1):1–27.Crossref, Google Scholar
• [10] Costa S, Morini F, Pasotti A, Pellegrini MA (2018) A problem on partial sums in Abelian groups. Discrete Math. 341(3):705–712.Crossref, Google Scholar
• [11] Cunningham WH (1986) On bounds for the metric TSP. Manuscript. School of Mathematics and Statistics, Carleton University, Ottawa.Google Scholar
• [12] 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
• [13] Garfinkel RS (1977) Minimizing wallpaper waste, part 1: A class of traveling salesman problems. Oper. Res. 25(5):741–751.Link, Google Scholar
• [14] Gilmore PC, Lawler EL, Shmoys DB (1985) Well-solved special cases. Lawler EL, Lenstra JK, Rinnooy Kan AHG, Shmoys DB, eds. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization (John Wiley and Sons, New York), 87–143.Google Scholar
• [15] Goemans MX (1995) Worst-case comparison of valid inequalities for the TSP. Math. Programming 69:335–349.Crossref, Google Scholar
• [16] Grötschel M (1980) On the monotone symmetric travelling salesman problem: Hypohamiltonian/hypotraceable graphs and facets. Math. Oper. Res. 5(2):285–292.Link, Google Scholar
• [17] Grötschel M, Padberg MW (1979) On the symmetric travelling salesman problem I: Inequalities. Math. Programming 16(1):265–280.Crossref, Google Scholar
• [18] Grötschel M, Padberg MW (1985) Polyhedral theory. Lawler EL, Lenstra J, Kan AHGR, Shmoys DB, eds. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization (John Wiley & Sons, New York), 251–306.Google Scholar
• [19] Grötschel M, Pulleyblank WR (1986) Clique tree inequalities and the symmetric travelling salesman problem. Math. Oper. Res. 11(4):537–569.Link, Google Scholar
• [20] Gutekunst SC, Williamson DP (2019) Characterizing the integrality gap of the subtour LP for the circulant traveling salesman problem. SIAM J. Discrete Math. 33(4):2452–2478.Crossref, Google Scholar
• [21] Held M, Karp RM (1970) The traveling-salesman problem and minimum spanning trees. Oper. Res. 18(6):1138–1162.Link, Google Scholar
• [22] Horak P, Rosa A (2009) On a problem of Marco Buratti. Electron. J. Combin. 16(1):R20.Crossref, Google Scholar
• [23] Karpinski M, Lampis M, Schmied R (2015) New inapproximability bounds for TSP. J. Comput. System Sci. 81(8):1665–1677.Crossref, Google Scholar
• [24] Medova E (1993) Using QAP bounds for the circulant TSP to design reconfigurable networks. Pardalos PM, Wolkowicz H, eds. Quadratic Assignment Related Problems, Proc. DIMACS Workshop, Rutgers University, vol. 16 (American Mathematical Society), 275–292.Google Scholar
• [25] Naddef D (1992) The binested inequalities for the symmetric traveling salesman polytope. Math. Oper. Res. 17(4):882–900.Link, Google Scholar
• [26] Naddef D (2007) Polyhedral theory and branch-and-cut algorithms for the symmetric TSP. Gutin G, Punnen AP, eds. The Traveling Salesman Problem and Its Variations (Springer, New York), 29–116.Crossref, Google Scholar
• [27] Naddef D, Rinaldi G (1991) The symmetric traveling salesman polytope and its graphical relaxation: Composition of valid inequalities. Math. Programming 51(1–3):359–400.Crossref, Google Scholar
• [28] Naddef D, Rinaldi G (1992) The crown inequalities for the symmetric traveling salesman polytope. Math. Oper. Res. 17(2):308–326.Link, Google Scholar
• [29] Padberg MW, Hong S (1980) On the symmetric traveling salesman problem: A computational study. Padberg MW, ed. Combinatorial Optimization (Springer, Berlin, Heidelberg), 78–107.Crossref, Google Scholar
• [30] Pasotti A, Pellegrini MA (2014) A new result on the problem of Buratti, Horak and Rosa. Discrete Math. 319(1):1–14.Crossref, Google Scholar
• [31] Reinelt G (1991) TSPLIB: A traveling salesman problem library. ORSA J. Comput. 3(4):376–384.Link, Google Scholar
• [32] 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
• [33] Williamson DP, Shmoys DB (2011) The Design of Approximation Algorithms (Cambridge University Press, New York).Crossref, Google Scholar
• [34] Wolsey LA (1980) Heuristic analysis, linear programming and branch and bound. Rayward-Smith VJ, ed. Combinatorial Optimization II (Springer, Berlin, Heidelberg), 121–134.Crossref, Google Scholar