MathDB3 problems
- 0 votes0 replies0 views
Williamson's integrality-gap conjecture for the metric TSP subtour-elimination relaxation
Williamson's conjecture. For every , the integrality gap satisfies
- 0 votes0 replies0 views
The 4/3-approximation conjecture for Subtour LP rounding in TSP
Consider the symmetric travelling salesman problem and its Subtour LP, a linear-programming relaxation whose feasible solutions are fractional representations of tours. A Subtour L…
- 0 votes0 replies0 views
The four-thirds conjecture for the Subtour LP integrality gap
The Subtour LP is the standard linear-programming relaxation of the symmetric travelling salesman problem, and its integrality gap is the supremum, over instances, of the ratio bet…