Résumé IA · arXiv: 2611.13585v1 · cs.DS
Approximating graphic TSP by b-matchings
L’essentiel
L’article présente StarMatch, un algorithme polynomial pour le TSP graphique dont la garantie est de 89/64 fois la valeur de la relaxation subtour.
Question
Peut-on améliorer la meilleure garantie connue pour le TSP graphique et resserrer l’écart d’intégralité de la relaxation subtour ? Les auteurs étudient aussi les garanties possibles sur des graphes fortement connexes.
Méthode
Les auteurs construisent, à partir d’un arbre DFS, un système d’étoiles d’arêtes supprimables, puis optimisent une correction de parité et le rétablissement de la connexité sur un polytope de T-joins à degrés bornés, résolu par b-appariement. Pour le cas général, ils partent d’un sommet optimal de la relaxation subtour, dont le support a au plus 2n−3 arêtes, et construisent un point réalisable du polytope afin d’obtenir la garantie 89/64 ; ils donnent aussi des analyses dédiées à certaines classes de graphes fortement connexes.
Résultats
-
Résultat
StarMatch fournit en temps polynomial une tournée de longueur au plus 89/64 fois la valeur de la relaxation subtour pour les graphes simples connexes.
Voir le passage dans l’article
We give a polynomial-time algorithm StarMatch based on the StarReconnectionLP that returns a tour of length $$\ell\leq\frac{89}{64}{\text{{SubtourLP}}(G)}=\left(\frac{7}{5}-\frac{3}{320}\right){\text{{SubtourLP}}(G)}.$$
-
Interprétation des auteurs
La garantie obtenue implique que l’écart d’intégralité de la relaxation subtour sur les instances graphiques est au plus 89/64.
Voir le passage dans l’article
This improves the long-standing ratio $\frac{7}{5}$ 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$.
-
Résultat
Pour les graphes 4-réguliers et 4-sommets-connexes, l’algorithme atteint une borne de tournée de 13n/10−3/5.
Voir le passage dans l’article
If $G$ is simple, $4$-regular, and $4$-vertex-connected, the StarReconnectionLP gives a tour of length at most $13n/10-3/5$.
-
Résultat
Pour les graphes k-sommets-connexes de degré maximum au plus k+1, avec k≥3, les deux formulations donnent une tournée de longueur au plus 4n/3−2/3.
Voir le passage dans l’article
If $G$ is simple and $k$-vertex-connected, where $k\geq 3$ and $\Delta(G)\leq k+1$, the StarDeletionLP and the StarReconnectionLP both give a tour of length at most $4n/3-2/3$.
-
Interprétation des auteurs
Le cadre de rétablissement de connexité autorise des T-joins plus flexibles que la formulation par suppression seule, ce qui permet aux auteurs d’améliorer leurs bornes.
Voir le passage dans l’article
This extra freedom of being able to optimize over all T-joins is crucial in our fractional constructions: we can use higher values on nonremovable edges when they help satisfy the Blossom cut inequalities, while accounting for both their added cost and the cost of reconnections.
Limites
- La conjecture d’un écart d’intégralité de 4/3 pour la relaxation subtour reste ouverte, y compris pour les instances graphiques.
Voir le passage dans l’article
The $4/3$ conjecture for the subtour relaxation, stated by Goemans [8, Conjecture 1], remains open even for graphic instances.
- Les garanties principales présentées pour le TSP graphique restent supérieures à 4/3 ; le résultat ne résout donc pas la conjecture générale.
Voir le passage dans l’article
This improves the long-standing ratio $\frac{7}{5}$ 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$.
Portée
Les auteurs présentent une amélioration de la garantie générale pour le TSP graphique et un cadre fondé sur les T-joins à degrés bornés, les étoiles supprimables et la reconnexion des sous-tournées. Ils soutiennent que cette approche améliore aussi les garanties pour plusieurs classes fortement connexes et peut servir de base à des améliorations ultérieures.
Rédigé par une IA à partir de l’article. Les passages cités sont vérifiés mot pour mot dans le texte analysé ; le reste peut contenir des erreurs.
Posez des questions sur cet article à notre assistant IA
Comment discuter avec cet article ? Guide illustré
Vous pouvez aussi discutez avec plusieurs papiers à la fois ici.
Gardez cette conversation — un compte gratuit conserve vos questions et réponses, vos collections d’articles et vos alertes.
Continuer avec Google Créer un compte gratuitOutils pour cet article
Outils avancés Premium
Pour suivre un domaine de près : alertes de citations, diapositives de journal club, comparaison des versions et envoi vers Zotero. Découvrir Premium
Parmi les 15 articles autour de celui-ci, le nom qui revient le plus : András Sebö (2 articles)
1 autre personne en signe plusieurs. La carte complète ajoute leurs institutions et leurs approches, d’après les articles des dernières années.
Les articles autour de celui-ci
Les voir sur une carteClassé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.
Avertissement : Notre outil de synthèse basé sur l'IA et l'assistant virtuel fournis sur ce site Web peuvent ne pas toujours fournir des résumés complets ou des réponses exactes. Nous vous encourageons à examiner attentivement et à évaluer le contenu généré pour vous assurer de sa qualité et de sa pertinence par rapport à vos besoins.