Tuesday, 13:15 - 13:40 h, Room: H 3010


Sylvia Boyd
The travelling salesman problem on cubic and subcubic graphs

Coauthors: René Sitters, Leen Stougie, Suzanne van der Ster


We study the travelling salesman problem (TSP) on the metric completion of cubic and subcubic graphs, which is known to be NP-hard. The problem
is of interest because of its relation to the famous 4⁄3 conjecture for metric TSP, which says that the integrality gap, i.e., the worst case
ratio between the optimal values of the TSP and its linear programming relaxation (the subtour elimination relaxation), is 4⁄3. We present the first algorithm for cubic graphs with approximation ratio 4⁄3. The proof uses polyhedral techniques in a surprising way, which is of independent interest. In fact we prove constructively that for any cubic graph on n vertices a tour of length 4n⁄3-2 exists, which also implies the 4⁄3 conjecture, as an upper bound, for this class of graph-TSP.


Talk 1 of the invited session Tue.2.H 3010
"Travelling salesman problem I" [...]
Cluster 1
"Approximation & online algorithms" [...]


  Payday Loans In Illinois. But at the same time, it acts only with sexual arousal. Buy Viagra has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.