Résumé IA · arXiv: 2611.13585v1 · cs.DS

Approximating graphic TSP by b-matchings

Swati Gupta, Mehrdad Sohrabi, Levent Tunçel
Article original Soumis à arXiv le 10 Nov. 2026 72 pages, 30 figures Licence : NONEXCLUSIVE-DISTRIB 1.0 Aussi en : en

Comment lire ce résumé ? Guide illustré

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.

Mots clés générés par l'IA : voyageur de commerce graphique relaxation subtour étoiles supprimables jointure de T écart d’intégralité

Pour aller plus loin

  • Résumé Complet
  • Résumé vulgarisé
  • Article de blog
  • Abstract original
L’article étudie le problème du voyageur de commerce graphique. Étant donné un graphe connexe non pondéré, il s’agit de construire une tournée de longueur minimale, la distance entre deux sommets étant définie comme la longueur de leur plus court chemin dans le graphe. Les auteurs cherchent notamment à améliorer l’approximation fondée sur la relaxation linéaire dite « relaxation subtour » et à réduire l’écart entre la valeur de cette relaxation et celle d’une tournée optimale. Avant ces travaux, la meilleure garantie générale annoncée était de 7/5, soit 1,4. La méthode repose sur des systèmes d’« étoiles supprimables », construits à partir d’un arbre de parcours en profondeur (DFS). Chaque étoile regroupe des arêtes incidentes à un même sommet. On peut en supprimer plusieurs tout en préservant la connexité, à condition d’en conserver au moins une. Les auteurs ramènent ensuite le choix de la correction de parité et des arêtes à supprimer à un problème de jointure de T (T-join) assorti de bornes de degré. Cette formulation repose sur un polytope de b-appariements, qui permet une optimisation en temps polynomial. Une extension, appelée StarReconnectionLP, autorise la sélection complète d’une étoile, à condition de comptabiliser le coût de deux copies d’une arête pour rétablir la connexité. Les garanties sont établies en construisant des points réalisables dans ce polytope et en contrôlant leur coût à l’aide des contraintes de la relaxation subtour. Le résultat général principal est l’algorithme polynomial StarMatch, qui produit une tournée de longueur au plus égale à 89/64, soit 1,390625, fois la valeur de la relaxation subtour. Il améliore ainsi la garantie de 1,4 et établit que, pour les instances graphiques, l’écart d’intégralité de cette relaxation est au plus 89/64. Pour obtenir cette borne, les auteurs combinent deux constructions de points réalisables : l’une dépend de la solution de la relaxation subtour, tandis que l’autre attribue des valeurs distinctes aux arêtes de l’arbre et aux arêtes de retour. Leur moyenne pondérée permet de contrôler simultanément les coûts de sélection et de reconnexion. Le cadre proposé fournit également de meilleures garanties pour certaines classes de graphes. Pour les graphes simples, 4-réguliers et 4-connexes par sommets, il garantit une approximation de 13/10, soit 1,3, contre 4/3 auparavant. Pour les graphes k-connexes par sommets dont le degré maximal est au plus k+1, pour tout k ≥ 3, la garantie est de 4/3. Ces résultats reposent sur un DFS arbitraire dans les classes considérées. L’article montre aussi que, pour un arbre DFS fixé, les formulations proposées sont au moins aussi performantes que certaines garanties du cadre de circulation de Mömke–Svensson. Les auteurs évoquent par ailleurs des améliorations potentielles, qu’ils distinguent de leurs résultats principaux : des preuves vérifiées à l’aide de Lean sont annoncées pour des ratios d’environ 1,38575 dans le cas général et de 9/7 pour les graphes 4-réguliers et 4-connexes. Toutefois, le texte ne présente pas ces démonstrations en détail ; elles ne remplacent donc pas les garanties établies de 89/64 et de 13/10. La portée des résultats se limite au problème graphique non pondéré et aux classes de graphes précisées.

Cette synthèse vous a-t-elle été utile ?

Note : 0

Pourquoi avons-nous besoin de votes ?

Les votes sont utilisés pour déterminer si nous devons réexécuter nos outils de synthèse. Si le compte atteint -10, nos outils peuvent être redémarrés.

Figures et graphiques

Posez une question sur une figure en indiquant son numéro ou en utilisant son bouton de question pour demander une analyse visuelle. Au maximum deux figures et quatre panneaux par question. Les valeurs lues sur les graphiques sont approximatives ; vérifiez les données originales.

Instructions pour utiliser l'assistant IA ?

Outils pour cet article

Expliquer autrement 1 réécriture gratuite restante aujourd'hui
Enregistrer dans une collection Regroupez des articles en collections pour les comparer, les interroger et les exporter. Continuer avec Google Créer un compte gratuit Se connecter

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

Zotero Guide Zotero
Alertes de citation Guide des alertes de citations
Qui travaille dessus ?

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.

Continuer avec Google Créez un compte gratuit : votre première carte est offerte
Lettre hebdomadaire Présenté dans « Informatique hors IA cette semaine » du 16 novembre 2026. Informatique hors IA cette semaine : les coûts cachés des réseaux et les limites repoussées des algorithmes · En recevoir une par email gratuitement

Les articles autour de celui-ci

Les voir sur une carte

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

  1. Très proche Autre approche du problème
    Approximating Graphic TSP by Matchings
    Tobias 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…

  2. Très proche Autre approche du problème
    4/3-Approximation of Graphic TSP
    A. Ç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.

  3. Très proche Même question
    A -approximation algorithm for Graphic TSP in cubic bipartite graphs
    Jeremy 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.

  4. Très proche Même question
    Graphic TSP in Cubic Graphs
    Z. 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.

  5. Très proche* Même question
    Approximating Regular Graphic TSP in near linear time
    Ashish 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.

  6. Très proche Autre approche du problème
    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 subgraphs
    Andrá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…

  7. Proche Contexte plus large
    An LP-based 3/2-approximation algorithm for the graphic s-t path TSP
    Zhihan 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}.

  8. Proche* Autre approche du problème
    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 subgraphs
    Andrá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.

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.

Le guide illustré des articles autour d’un article

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.