Some Necessary Conditions and a General Sufficiency Condition for the Validity of A Gilmore-Gomory Type Patching Scheme for the Traveling Salesman Problem - Baki, M.; Kabadi, S. (Algorithmic Operations Research)

(untitled) (Preeminent Academic Facets Inc., 2007)
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.