2 problems

0 votes0 replies0 views
The bidirected cut relaxation integrality-gap conjecture for Steiner tree
Consider the efficiently solvable class of bidirected relaxations for the Steiner tree problem, whose characteristic representative is the bidirected cut relaxation. The bidirected…
Conjectureopenapproximation-algorithms linear-programming-relaxations steiner-treesarXiv posted 2 days ago
0 votes0 replies0 views
The 4/3 conjecture for the subtour relaxation of metric TSP
Let a tour be a traveling-salesman tour, and let the subtour relaxation be the standard linear-programming relaxation whose optimum value is a lower bound on the length of an optim…
Conjectureopenapproximation-algorithms linear-programming-relaxations traveling-salesman-problemarXiv posted 2 days ago

The bidirected cut relaxation integrality-gap conjecture for Steiner tree