Exécution de notre outil de synthèse sur un nouvel article
Vérifiez l’article ci-dessous, puis lancez sa synthèse.
4/3-Approximation of Graphic TSP
Ali Çivril
arXiv: 2305.05411v1 (cs.DS)
This was an early and insufficiently verified attempt. Errors affecting the main results were later identified, and the manuscript has been withdrawn
Licence : CC BY-NC-ND 4.0
Résumé : 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.
Soumis à arXiv le 21 Jul. 2026