Exécution de notre outil de synthèse sur un nouvel article
Vérifiez l’article ci-dessous, puis lancez sa synthèse.
Improved integrality gap upper bounds for TSP with distances one and two
Matthias Mnich, Tobias Mömke
Résumé : We study the structure of solutions to linear programming formulations for the traveling salesperson problem (TSP). We perform a detailed analysis of the support of the subtour elimination linear programming relaxation, which leads to algorithms that find 2-matchings with few components in polynomial time. The number of components directly leads to integrality gap upper bounds for the TSP with distances one and two, for both undirected and directed graphs. Our main results for fractionally Hamiltonian instances are: - For undirected instances we obtain an integrality gap upper bound of 5/4 without any further restrictions, of 7/6 if the optimal LP solution is half-integral, and of 10/9 if there is an optimal solution that is a basic solution of the fractional 2-matching polytope. - For directed instances we obtain an integrality gap upper bound of 3/2, and of 4/3 if given an optimal 1/2-integral solution. Additionally, we show that relying on the structure of the support is not an artefact of our algorithm, but is necessary under standard complexity-theoretic assumptions: we show that finding improved solutions via local search is W[1]-hard for k-edge change neighborhoods even for the TSP with distances one and two, which strengthens a result of Dániel Marx.