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

DOI10.1016/j.disopt.2011.05.002zbMath1235.90124OpenAlexW2068748054MaRDI QIDQ408370

J. Herrera, H. S. Yoon

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)

Related Items

A 4/3-approximation algorithm for half-integral cycle cut instances of the TSP, Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices, 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, On the generation of metric TSP instances with a large integrality gap by branch-and-cut, Shorter tours and longer detours: uniform covers and a bit beyond, The salesman's improved tours for fundamental classes, Unnamed Item, Efficient constructions of convex combinations for 2-edge-connected subgraphs on fundamental classes, Unnamed Item

Cites Work

• Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices
• Minimum-weight two-connected spanning networks
• Analyzing the Held-Karp TSP bound: A monotonicity property with application
• Matchings in regular graphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems
• Worst-case comparison of valid inequalities for the TSP
• 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
• The traveling salesman problem on a graph and some related integer polyhedra
• Heuristic analysis, linear programming and branch and bound
• On the Integrality Ratio for the Asymmetric Traveling Salesman Problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item