2014-01-01

# 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 | |
---|---|

THEME | Logistics (theme 3) |

Publisher | Springer |

Persistent URL | dx.doi.org/10.1007/s10107-012-0620-1 |

Journal | Mathematical Programming |

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