The travelling salesman problem on cubic and subcubic graphs

S.M. Boyd, R.A. Sitters, S.L. van der Ster, L. Stougie

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

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.
LanguageEnglish
Pages227-245
JournalMathematical Programming
Volume144
Issue number1-2
DOIs
Publication statusPublished - 2014

Fingerprint

Traveling salesman problem
Travelling salesman problems
Graph in graph theory
Cubic Graph
Derandomization
Metric
Linear Programming Relaxation
Integrality
Multigraph
Approximation algorithms
Approximation
Linear programming
Completion
Elimination
Approximation Algorithms
Trivial
NP-complete problem
Upper bound
Imply
Optimization

Cite this

Boyd, S.M. ; Sitters, R.A. ; van der Ster, S.L. ; Stougie, L. / The travelling salesman problem on cubic and subcubic graphs. In: Mathematical Programming. 2014 ; Vol. 144, No. 1-2. pp. 227-245.
@article{0b055ba8e2b04ad5b2a98129d063f684,
title = "The travelling salesman problem on cubic and subcubic graphs",
abstract = "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{\"o}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{\"o}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. {\circledC} 2012 Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society.",
author = "S.M. Boyd and R.A. Sitters and {van der Ster}, S.L. and L. Stougie",
year = "2014",
doi = "10.1007/s10107-012-0620-1",
language = "English",
volume = "144",
pages = "227--245",
journal = "Mathematical Programming",
issn = "0025-5610",
publisher = "Springer-Verlag GmbH and Co. KG",
number = "1-2",

}

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

In: Mathematical Programming, Vol. 144, No. 1-2, 2014, p. 227-245.

Research output: Contribution to JournalArticleAcademicpeer-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

T2 - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 1-2

ER -