Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices
From MaRDI portal
Publication:408370
DOI10.1016/J.DISOPT.2011.05.002zbMATH Open1235.90124OpenAlexW2068748054MaRDI QIDQ408370FDOQ408370
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
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
Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)
Cites Work
- The traveling salesman problem on a graph and some related integer polyhedra
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Graph theory with applications
- Worst-case comparison of valid inequalities for the TSP
- Minimum-weight two-connected spanning networks
- Structure of the extreme points of the subtour elimination polytope of the STSP
- On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems
- Title not available (Why is that?)
- On the Integrality Ratio for the Asymmetric Traveling Salesman Problem
- Title not available (Why is that?)
- Heuristic analysis, linear programming and branch and bound
- Analyzing the Held-Karp TSP bound: A monotonicity property with application
- Title not available (Why is that?)
- Matchings in regular graphs
- A new bound for the ratio between the 2-matching problem and its linear programming relaxation
- Finding the exact integrality gap for small traveling salesman problems
- Not Every GTSP Facet Induces an STSP Facet
- Title not available (Why is that?)
- Title not available (Why is that?)
- Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices
Cited In (17)
- Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices
- Computing compatible tours for the symmetric traveling salesman problem
- On common edges in optimal solutions to traveling salesman and other optimization problems
- Title not available (Why is that?)
- A proof of the Boyd-Carr conjecture
- 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
- A new bound for the ratio between the 2-matching problem and its linear programming relaxation
- Title not available (Why is that?)
- Matroid-based TSP rounding for half-integral solutions
- A 4/3-approximation algorithm for half-integral cycle cut instances of the TSP
- Structure of the extreme points of the subtour elimination polytope of the STSP
- Efficient constructions of convex combinations for 2-edge-connected subgraphs on fundamental classes
- 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
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)
