Résumés
Abstract
One of the most celebrated polynomially solvable cases of the TSP is the Gilmore-Gomory TSP. The patching scheme for the problem developed by Gilmore and Gomory has several interesting features. Its generalization, called the GG-scheme, has been studied by several researchers and polynomially testable sufficiency conditions for its validity have been given, leading to polynomial schemes for large subclasses of the TSP. A good characterization of the subclass of the TSP for which the GG-scheme produces an optimal solution, is an outstanding open problem of both theoretical and practical significance. We give some necessary conditions and a new, polynomially testable sufficiency condition for the validity of the GG-scheme that properly includes all previously known such conditions.
Keywords:
- Traveling salesman problem,
- Gilmore-Gomory TSP,
- Patching Scheme,
- Polynomially solvable cases
Veuillez télécharger l’article en PDF pour le lire.
Télécharger