Finding the Exact Integrality Gap for Small Traveling Salesman Problems

References

• Boyd S., Carr R. Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices. (1996) . Technical Report TR-96-12, University of Ottawa, Ottawa, CanadaGoogle Scholar
• Boyd S., Carr R. A new bound for the ratio between the 2-matching problem and its linear programming relaxation. Math. Programming Ser. A (1999) 86:499–514Crossref, Google Scholar
• Boyd S., Elliott-Magwood P. Computing the integrality gap of the asymmetric travelling salesman problem. Proc. GRACO 2005, Electronic Notes in Discrete Mathematics (2005) 19(Elsevier, Amsterdam) 241–247Crossref, Google Scholar
• Boyd S., Elliott-Magwood P. The structure of the extreme points of the subtour elimination polytope of the STSP. (2007) . Technical Report TR-2007-09, University of Ottawa, Ottawa, CanadaGoogle Scholar
• Boyd S., Pulleyblank W. R. Optimizing over the subtour polytope of the travelling salesman problem. Math. Programming (1991) 49:163–187Crossref, Google Scholar
• Carr R., Ravi R. A new bound for the 2-edge connected subgraph problem. Proc. Integer Programming Combin. Optim. (IPCO), Lecture Notes in Computer Science (1998) (Springer, London) 112–125Crossref, Google Scholar
• Carr R., Vempala S. Towards a 4/3 approximation for the asymmetric traveling salesman problem. Proc. Eleventh Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (2000) (ACM Press, New York) 116–125Google Scholar
• Charikar M., Goemans M. X., Karloff H. On the integrality ratio for asymmetric TSP. Math. Oper. Res. (2006) 31:245–252Link, Google Scholar
• Christof T., Löbel A., Stoer M. PORTA, A polyhedron representation transformation algorithm. (1997) . http://www.zib.de/Optimization/Software/Porta/index.htmlGoogle Scholar
• Christofides N. Worst case analysis of a new heuristic for the traveling salesman problem. (1976) . Report 388, Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh, PAGoogle Scholar
• Grötschel M., Lovasz L., Schrijver A.Geometric Algorithms and Combinatorial Optimization (1988) (Springer-Verlag, Berlin) Crossref, Google Scholar
• Lawler E. L., Lenstra J. K., Rinnooy-Kan A. H. G., Shmoys D. B.The Travelling Salesman Problem: A Guided Tour of Combinatorial Optimization (1985) (Wiley, New York) Google Scholar
• McKay B. Nauty user's guide (Version 1.5). (1990) . Technical Report TR-CS-90-02, Department of Computer Science, Australia National University, CanberraGoogle Scholar
• Shmoys D. B., Williamson D. P. Analyzing the Held-Karp TSP bound: A monotonicity property with application. Inf. Process. Lett. (1990) 35:281–285Crossref, Google Scholar
• Wolsey L. A. Heuristic analysis, linear programming and branch and bound. Math. Programming Stud. (1980) 13:121–134Crossref, Google Scholar