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

MaRDI QIDQ2999650zbMATH OpenFDO

Authors Sylvia Boyd, Paul Elliott-Magwood

Publication date 16 May 2011

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)

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

Cited in

(6)

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

Describes a project that uses

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)