Towards Improving Christofides Algorithm on Fundamental Classes by Gluing Convex Combinations of Tours - Optimisation Combinatoire Accéder directement au contenu
Article Dans Une Revue Mathematical Programming, Series A Année : 2023

Towards Improving Christofides Algorithm on Fundamental Classes by Gluing Convex Combinations of Tours

Résumé

We present a new approach for gluing tours over certain tight, 3-edge cuts. Gluing over 3-edge cuts has been used in algorithms for finding Hamilton cycles in special graph classes and in proving bounds for 2-edge-connected subgraph problem, but not much was known in this direction for gluing connected multigraphs. We apply this approach to the traveling salesman problem (TSP) in the case when the objective function of the subtour elimination relaxation is minimized by a θ-cyclic point: x e ∈ {0, θ, 1 − θ, 1}, where the support graph is subcubic and each vertex is incident to at least one edge with x-value 1. Such points are sufficient to resolve TSP in general. For these points, we construct a convex combination of tours in which we can reduce the usage of edges with x-value 1 from the 3 2 of Christofides algorithm to 3 2 − θ 10 while keeping the usage of edges with fractional x-value the same as Christofides algorithm. A direct consequence of this result is for the Uniform Cover Problem for TSP: In the case when the objective function of the subtour elimination relaxation is minimized by a 2 3-uniform point: x e ∈ {0, 2 3 }, we give a 17 12-approximation algorithm for TSP. For such points, this lands us halfway between the approximation ratios of 3 2 of Christofides algorithm and 4 3 implied by the famous "four-thirds conjecture".
Fichier principal
Vignette du fichier
1907.02120.pdf (582.43 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03101691 , version 1 (07-01-2021)

Identifiants

Citer

Arash Haddadan, Alantha Newman. Towards Improving Christofides Algorithm on Fundamental Classes by Gluing Convex Combinations of Tours. Mathematical Programming, Series A, 2023, 198, pp.595-620. ⟨10.1007/s10107-022-01784-w⟩. ⟨hal-03101691⟩
94 Consultations
39 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More