2-Matchings, the Traveling Salesman Problem, and the Subtour LP: A Proof of the Boyd-Carr Conjecture

DOI10.1287/moor.2013.0608zbMath1291.90132OpenAlexW1990900182WikidataQ123334378 ScholiaQ123334378MaRDI QIDQ5169706

Anke van Zuylen, David P. Williamson, Frans Schalekamp

Publication date: 11 July 2014

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/31357033a307f29f7615376248ee7fa4ba2f3fec

zbMATH Keywords

linear programmingtraveling salesman problemintegrality gap2-matchingsubtour eliminationfractional 2-matching

Mathematics Subject Classification ID

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

Related Items (10)

Matroid-based TSP rounding for half-integral solutions ⋮ An optimal rounding for half-integral weighted minimum strongly connected spanning subgraph ⋮ A $\frac{4}{3}$-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case ⋮ A 4/3-approximation algorithm for half-integral cycle cut instances of the TSP ⋮ Towards improving Christofides algorithm on fundamental classes by gluing convex combinations of tours ⋮ Hidden Hamiltonian Cycle Recovery via Linear Programming ⋮ The salesman's improved tours for fundamental classes ⋮ Improved integrality gap upper bounds for traveling salesperson problems with distances one and two ⋮ Unnamed Item ⋮ Efficient constructions of convex combinations for 2-edge-connected subgraphs on fundamental classes

This page was built for publication: 2-Matchings, the Traveling Salesman Problem, and the Subtour LP: A Proof of the Boyd-Carr Conjecture