Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices

DOI10.1016/J.DISOPT.2011.05.002MaRDI QIDQ408370zbMATH OpenOpenAlexFDO

Authors Sylvia Boyd, Robert Carr

Publication date 5 April 2012

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disopt.2011.05.002

zbMATH Keywords

approximation algorithmtraveling salesman problem2-matching

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Recommendations

• scientific article; zbMATH DE number 1187146
• A note on the traveling salesman problem
• 2-matchings, the traveling salesman problem, and the subtour LP: a proof of the Boyd-Carr conjecture
• On the integrality gap of the subtour LP for the \(1,2\)-TSP
• On the integrality gap of the subtour LP for the 1,2-TSP

Cites work

• scientific article; zbMATH DE number 5158509 (Why is no real title available?)
• scientific article; zbMATH DE number 3904331 (Why is no real title available?)
• scientific article; zbMATH DE number 3926663 (Why is no real title available?)
• scientific article; zbMATH DE number 1187146 (Why is no real title available?)
• scientific article; zbMATH DE number 795217 (Why is no real title available?)
• A new bound for the ratio between the 2-matching problem and its linear programming relaxation
• Analyzing the Held-Karp TSP bound: A monotonicity property with application
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices
• Finding the exact integrality gap for small traveling salesman problems
• Graph theory with applications
• Heuristic analysis, linear programming and branch and bound
• Matchings in regular graphs
• Minimum-weight two-connected spanning networks
• Not Every GTSP Facet Induces an STSP Facet
• On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems
• On the Integrality Ratio for the Asymmetric Traveling Salesman Problem
• Structure of the extreme points of the subtour elimination polytope of the STSP
• The traveling salesman problem on a graph and some related integer polyhedra
• Worst-case comparison of valid inequalities for the TSP

Cited in

(17)

• Shorter tours and longer detours: uniform covers and a bit beyond
• The salesman's improved tours for fundamental classes
• Towards improving Christofides algorithm on fundamental classes by gluing convex combinations of tours
• Fractional decomposition tree algorithm: a tool for studying the integrality gap of integer programs
• scientific article; zbMATH DE number 7525493 (Why is no real title available?)
• Computing compatible tours for the symmetric traveling salesman problem
• Structure of the extreme points of the subtour elimination polytope of the STSP
• A proof of the Boyd-Carr conjecture
• Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices
• A 4/3-approximation algorithm for half-integral cycle cut instances of the TSP
• 2-matchings, the traveling salesman problem, and the subtour LP: a proof of the Boyd-Carr conjecture
• On the generation of metric TSP instances with a large integrality gap by branch-and-cut
• On common edges in optimal solutions to traveling salesman and other optimization problems
• A new bound for the ratio between the 2-matching problem and its linear programming relaxation
• Efficient constructions of convex combinations for 2-edge-connected subgraphs on fundamental classes
• scientific article; zbMATH DE number 1187146 (Why is no real title available?)
• Matroid-based TSP rounding for half-integral solutions

This page was built for publication: Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices

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