The integrality gap of the traveling salesman problem is 43 if the LP solution has at most n + 6 non-zero components
From MaRDI portal
Publication:7349451
Cites work
- 2-matchings, the traveling salesman problem, and the subtour LP: a proof of the Boyd-Carr conjecture
- A (slightly) improved approximation algorithm for metric TSP
- A (slightly) improved bound on the integrality gap of the subtour LP for TSP
- A \(\frac{4}{3} \)-approximation algorithm for half-integral cycle cut instances of the TSP
- An improved approximation algorithm for TSP in the half integral case
- Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices
- Finding the exact integrality gap for small traveling salesman problems
- Hard to solve instances of the Euclidean traveling salesman problem
- Heuristic analysis, linear programming and branch and bound
- Lower bounds on the integrality ratio of the subtour LP for the traveling salesman problem
- Matroid-based TSP rounding for half-integral solutions
- On the generation of metric TSP instances with a large integrality gap by branch-and-cut
- On the integrality ratio of the subtour LP for Euclidean TSP
- Optimizing over the subtour polytope of the travelling salesman problem
- Removing and adding edges for the traveling salesman problem
- Solution of a Large-Scale Traveling-Salesman Problem
- Structure of the extreme points of the subtour elimination polytope of the STSP
- The salesman's improved tours for fundamental classes
- The traveling salesman problem on a graph and some related integer polyhedra
- TSP on cubic and subcubic graphs
- Worst-case comparison of valid inequalities for the TSP
This page was built for publication: The integrality gap of the traveling salesman problem is \(\frac{4}{3}\) if the LP solution has at most \(n + 6\) non-zero components
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7349451)
