Improved integrality gap upper bounds for traveling salesperson problems with distances one and two
From MaRDI portal
Publication:1754106
DOI10.1016/j.ejor.2017.09.036zbMath1403.90643OpenAlexW2758192806MaRDI QIDQ1754106
Publication date: 30 May 2018
Published in: European Journal of Operational Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ejor.2017.09.036
Related Items (1)
Cites Work
- Optimizing over the subtour polytope of the travelling salesman problem
- Searching the \(k\)-change neighborhood for TSP is W[1-hard]
- An approximation algorithm for the asymmetric travelling salesman problem with distances one and two
- Which problems have strongly exponential complexity?
- Worst-case comparison of valid inequalities for the TSP
- On the integrality gap of the subtour LP for the 1,2-TSP
- Approximating maximum weight cycle covers in directed graphs with weights zero and one
- TSP with bounded metrics
- Tight lower bounds for certain parameterized NP-hard problems
- New Inapproximability Bounds for TSP
- On the Integrality Gap of the Subtour LP for the 1,2-TSP
- TSP on Cubic and Subcubic Graphs
- 8/7-approximation algorithm for (1,2)-TSP
- Heuristic analysis, linear programming and branch and bound
- The Traveling Salesman Problem with Distances One and Two
- 2-Matchings, the Traveling Salesman Problem, and the Subtour LP: A Proof of the Boyd-Carr Conjecture
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Integer Programming: Methods, Uses, Computations
- Fundamentals of Computation Theory
- Approximating Graphic TSP by Matchings
- The Traveling-Salesman Problem and Minimum Spanning Trees
This page was built for publication: Improved integrality gap upper bounds for traveling salesperson problems with distances one and two
