### Abstract

Original language | English |
---|---|

Pages (from-to) | 227-245 |

Journal | Mathematical Programming |

Volume | 144 |

Issue number | 1-2 |

DOIs | |

Publication status | Published - 2014 |

### Fingerprint

### Cite this

*Mathematical Programming*,

*144*(1-2), 227-245. https://doi.org/10.1007/s10107-012-0620-1

}

*Mathematical Programming*, vol. 144, no. 1-2, pp. 227-245. https://doi.org/10.1007/s10107-012-0620-1

**The travelling salesman problem on cubic and subcubic graphs.** / Boyd, S.M.; Sitters, R.A.; van der Ster, S.L.; Stougie, L.

Research output: Contribution to Journal › Article › Academic › peer-review

TY - JOUR

T1 - The travelling salesman problem on cubic and subcubic graphs

AU - Boyd, S.M.

AU - Sitters, R.A.

AU - van der Ster, S.L.

AU - Stougie, L.

PY - 2014

Y1 - 2014

N2 - 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 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. 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. © 2012 Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society.

AB - 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 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. 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. © 2012 Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society.

U2 - 10.1007/s10107-012-0620-1

DO - 10.1007/s10107-012-0620-1

M3 - Article

VL - 144

SP - 227

EP - 245

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 1-2

ER -