A proof of the Boyd-Carr conjecture

MaRDI QIDQ5743492zbMATH OpenFDO

Authors Frans Schalekamp, David P. Williamson, Anke van Zuylen

Publication date 10 May 2019

Full work available at URL https://arxiv.org/abs/1107.1628, https://dl.acm.org/citation.cfm?id=2095233

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Fractional graph theory, fuzzy graph theory (05C72) Linear programming (90C05) Combinatorial optimization (90C27)

Recommendations

• 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
• Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices
• A new bound for the ratio between the 2-matching problem and its linear programming relaxation

Cites work

• A new bound for the ratio between the 2-matching problem and its linear programming relaxation
• A Randomized Rounding Approach to the Traveling Salesman Problem
• Analyzing the Held-Karp TSP bound: A monotonicity property with application
• Approximating Graphic TSP by Matchings
• 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
• Heuristic analysis, linear programming and branch and bound
• scientific article; zbMATH DE number 2064412 (Why is no real title available?)
• Integer Programming: Methods, Uses, Computations
• Matchings in regular graphs
• Maximum matching and a polyhedron with 0,1-vertices
• On the integrality gap of the subtour LP for the 1,2-TSP
• Optimum branchings
• Solution of a Large-Scale Traveling-Salesman Problem
• Structure of the extreme points of the subtour elimination polytope of the STSP
• Survivable networks, linear programming relaxations and the parsimonious property
• TSP on cubic and subcubic graphs
• Worst-case comparison of valid inequalities for the TSP

Cited in

(3)

• On a strong form of a conjecture of Boyle and Handelman
• 2-matchings, the traveling salesman problem, and the subtour LP: a proof of the Boyd-Carr conjecture
• TSP tours in cubic graphs: beyond 4/3

This page was built for publication: A proof of the Boyd-Carr conjecture

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