2014

# The traveling salesman problem on cubic and subcubic graphs

## Publication

### Publication

*
Mathematical Programming
,
Volume 144
p. 227-
245
*

We study the traveling 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 value of a TSP instance and that of 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 TeX vertices a tour of length TeX exists, which also implies the 4/3-conjecture, as an upper bound, for this class of graph-TSP. Recently, Mömke and Svensson presented an algorithm that gives a 1.461-approximation for graph-TSP on general graphs and as a side result a 4/3-approximation algorithm for this problem on subcubic graphs, also settling the 4/3-conjecture for this class of graph-TSP. The algorithm by Mömke and Svensson is initially randomized but the authors remark that derandomization is trivial. We will present a different way to derandomize their algorithm which leads to a faster running time. All of the latter also works for multigraphs.

Additional Metadata | |
---|---|

Springer | |

doi.org/10.1007/s10107-012-0620-1 | |

Mathematical Programming | |

Organisation | Networks and Optimization |

Boyd, S., Sitters, R., van der Ster, S., & Stougie, L. (2014). The traveling salesman problem on cubic and subcubic graphs. Mathematical Programming, 144, 227–245. doi:10.1007/s10107-012-0620-1 |