Approximating graphic TSP by b-matchings
Auteurs : Swati Gupta, Mehrdad Sohrabi, Levent Tunçel
Résumé scientifique
We give a polynomial-time algorithm for graphic TSP that returns a tour of length at most $\frac{89}{64}=\frac{7}{5}-\frac{3}{320}$ times the value of the subtour relaxation. This improves the long-standing ratio $\frac75$ of Sebő and Vygen and shows that the integrality gap of the subtour LP on graphic instances is at most $\frac{89}{64}\approx 1.3906$. We optimize a non-linear objective function over an odd-join polytope, which uses (i) a new removable system of edges, and (ii) reconnection of subtours if the graph is disconnected. This approach gives a $\frac{13}{10}$-approximation algorithm for $4$-regular $4$-vertex-connected graphs, improving the $\frac43$ of Newman, and a $\frac43$-approximation for $k$-vertex-connected graphs of maximum degree at most $k+1$, for every $k\ge 3$. For the general graphic TSP, we construct a feasible point in the odd-join polytope, using an optimal vertex from the Subtour linear programming relaxation of TSP, which helps us bound the approximation factor by 89/64.
Les articles autour de lui, par date et par proximité
Plus haut, c’est plus proche de cet article ; à gauche, c’est plus ancien. Les traits relient les articles proches entre eux : les groupes de traits sont des sous-thèmes. Sélectionnez un point pour voir pourquoi il est là. Retour au résumé de cet article
Les articles autour de celui-ci
Classés selon la proximité de leur titre et de leur résumé avec ceux de cet article. Sélectionnez-en pour les lire ensemble.
Les articles les plus proches
-
Approximating Graphic TSP by MatchingsTobias Moemke, O. Svensson · 2011 · IEEE Annual Symposium on Foundations of Computer Science · cité 117 fois · Pas encore résumé
Approximating Graphic TSP by Matchings utilise des appariements pour retirer des arêtes et obtenir une garantie de 1,461, tandis que cet article optimise un polytope d’odd-joins.
Résumé scientifique
We present a framework for approximating the metric TSP based on a novel use of matchings. Traditionally, matchings have been used to add edges in order to make a given graph Eulerian, whereas our approach also allows for the removal of certain edges leading to a decreased cost. For the TSP on graphic metrics (graph-TSP), the approach yields a 1.461-approximation algorithm with respect to the Held-Karp lower bound. For graph-TSP restricted to a class of graphs that contains degree three bounded and claw-free graphs, we show that the integrality gap of the Held-Karp relaxation matches the conjectured ratio 4/3. The framework allows for generalizations in a natural way and also leads to a 1.58…
-
4/3-Approximation of Graphic TSPA. Çivril · 2023 · arXiv.org · preprint, non relu par les pairs · Pas encore résumé
4/3-Approximation of Graphic TSP ajoute un couplage parfait aux sommets de degré impair d’un sous-graphe couvrant 2-arête-connexe, plutôt que d’optimiser un polytope d’odd-joins.
Résumé scientifique
We describe a $\frac{4}{3}$-approximation algorithm for the traveling salesman problem in which the distances between points are induced by graph-theoretical distances in an unweighted graph. The algorithm is based on finding a minimum cost perfect matching on the odd degree vertices of a carefully computed 2-edge-connected spanning subgraph.
-
A -approximation algorithm for Graphic TSP in cubic bipartite graphsJeremy Karp, R. Ravi · 2013 · Discrete Applied Mathematics · cité 17 fois · Pas encore résumé
A -approximation algorithm for Graphic TSP in cubic bipartite graphs étudie le TSP graphique sur des graphes bipartis réguliers et améliore ses garanties d’approximation.
Résumé scientifique
We prove new results for approximating Graphic TSP. Specifically, we provide a polynomial-time \frac{9}{7}-approximation algorithm for cubic bipartite graphs and a (\frac{9}{7}+\frac{1}{21(k-2)})-approximation algorithm for k-regular bipartite graphs, both of which are improved approximation factors compared to previous results. Our approach involves finding a cycle cover with relatively few cycles, which we are able to do by leveraging the fact that all cycles in bipartite graphs are of even length along with our knowledge of the structure of cubic graphs.
-
Graphic TSP in Cubic GraphsZ. Dvořák, D. Král', B. Mohar · 2016 · Symposium on Theoretical Aspects of Computer Science · cité 9 fois · Pas encore résumé
Graphic TSP in Cubic Graphs étudie les garanties d’approximation du TSP graphique sur les graphes cubiques, tandis que cet article traite aussi de classes particulières.
Résumé scientifique
We present a polynomial-time 9/7-approximation algorithm for the graphic TSP for cubic graphs, which improves the previously best approximation factor of 1.3 for 2-connected cubic graphs and drops the requirement of 2-connectivity at the same time. To design our algorithm, we prove that every simple 2-connected cubic n-vertex graph contains a spanning closed walk of length at most 9n/7-1, and that such a walk can be found in polynomial time.
-
Approximating Regular Graphic TSP in near linear timeAshish Chiplunkar, S. Vishwanathan · 2014 · arXiv.org · preprint, non relu par les pairs · Pas encore résumé
Approximating Regular Graphic TSP in near linear time porte sur l’approximation du TSP graphique régulier, une classe de graphes également étudiée ici.
-
Shorter tours by nicer ears: 7/5-approximation for the graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphsAndrás Sebö, J. Vygen · 2012 · arXiv.org · cité 159 fois · Pas encore résumé
Shorter tours by nicer ears obtient une garantie de 7/5 pour le TSP graphique par décomposition en oreilles, contre 89/64 par optimisation d’odd-joins ici.
Résumé scientifique
We prove new results for approximating the graph-TSP and some related problems. We obtain polynomial-time algorithms with improved approximation guarantees.For the graph-TSP itself, we improve the approximation ratio to 7/5. For a generalization, the minimum T-tour problem, we obtain the first nontrivial approximation algorithm, with ratio 3/2. This contains the s-t-path graph-TSP as a special case. Our approximation guarantee for finding a smallest 2-edge-connected spanning subgraph is 4/3.The key new ingredient of all our algorithms is a special kind of ear-decomposition optimized using forest representations of hypergraphs. The same methods also provide the lower bounds (arising from LP r…
-
An LP-based 3/2-approximation algorithm for the graphic s-t path TSPZhihan Gao · 2013 · arXiv.org · preprint, non relu par les pairs · cité 3 fois · Pas encore résumé
An LP-based 3/2-approximation algorithm for the graphic s-t path TSP traite la version chemin du TSP graphique, plutôt que le problème de tournée étudié ici.
Résumé scientifique
We design a new LP-based algorithm for the graphic $s$-$t$ path Traveling Salesman Problem (TSP), which achieves the best approximation factor of 1.5. The algorithm is based on the idea of narrow cuts due to An, Kleinberg, and Shmoys. It partly answers an open question of Seb\H{o}.
-
Shorter tours by nicer ears: 7/5-Approximation for the graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphsAndrás Sebö, J. Vygen · 2014 · Combinatorica · cité 86 fois · Pas encore résumé
Shorter tours by nicer ears obtient une garantie de 7/5 par décomposition en oreilles, tandis que cet article améliore la garantie à 89/64 avec les odd-joins.
Aller plus loin
Comment ces articles sont-ils trouvés ?
Nous comparons le titre et le résumé de cet article avec ceux de tous les articles résumés sur ce site, et avec les articles que Semantic Scholar recommande, ceux qu’il cite et ceux qui le citent (pour un article très cité, ses citations les plus récentes et, depuis OpenAlex, les plus citées). Parmi les travaux antérieurs et les suites, les articles qui s’utilisent en profondeur, une méthode qu’il utilise et les suites très citées remontent un peu. Les niveaux (très proche, proche, apparenté) viennent de la similarité des textes, pas d’un jugement de qualité ; * signale un article sans résumé, comparé par son titre. La phrase sous un article est écrite par une IA à partir des deux résumés : vérifiez-la dans les articles. Un article jugé hors sujet par trois lecteurs quitte la liste.
Mis à jour le 16 novembre 2026.