Structure of the extreme points of the subtour elimination polytope of the STSP

zbMATH Open1223.90050MaRDI QIDQ2999650FDOQ2999650

Authors: Sylvia Boyd, Paul Elliott-Magwood 

Publication date: 16 May 2011

Recommendations

• Finding the exact integrality gap for small traveling salesman problems
• scientific article; zbMATH DE number 2086915
• A note on the traveling salesman problem
• On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems
• Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices

zbMATH Keywords

approximation algorithmspolyhedral combinatoricsgraph and network algorithms

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Cited In (6)

• Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices
• A proof of the Boyd-Carr conjecture
• Computing assortative mixing by degree with the \(s\)-metric in networks using linear programming
• Finding the exact integrality gap for small traveling salesman problems
• On the generation of metric TSP instances with a large integrality gap by branch-and-cut
• Title not available (Why is that?)

Uses Software

• nauty

This page was built for publication: Structure of the extreme points of the subtour elimination polytope of the STSP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2999650)