Some Necessary Conditions and a General Sufficiency Condition for the Validity of A Gilmore-Gomory Type Patching Scheme for the Traveling

Authors

  • M. F. Baki Odette School of Business, University of Windsor, Windsor, Ontario, Canada N9B 3P4
  • S. N. Kabadi Faculty of Business Administration, University of New Brunswick, Fredericton, N.B., Canada E3B 5A3

Keywords:

Traveling salesman problem, Gilmore-Gomory TSP, Patching Scheme, Polynomially solvable cases

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. Key words: Traveling salesman problem, Gilmore-Gomory TSP, Patching Scheme, Polynomially solvable cases

Downloads

Published

2007-02-07

How to Cite

Baki, M. F., & Kabadi, S. N. (2007). Some Necessary Conditions and a General Sufficiency Condition for the Validity of A Gilmore-Gomory Type Patching Scheme for the Traveling. Algorithmic Operations Research, 2(1). Retrieved from https://journals.lib.unb.ca/index.php/AOR/article/view/2731

Issue

Vol. 2 No. 1 (2007)

Section

Articles

License

The copyright of the submitted article is hereby transferred to “Preeminent Academic Facets Inc. (the “publisher”) to the extent possible by the laws in the respective countries of the author(s). The author(s) retain all other rights including the following: 1. Any patents and trademark rights. 2. Right to post a pre-print version of the paper on the author’s personal website which is not used for commercial purposes. The author(s) warrant that the work is original, it has not been published elsewhere, it is not currently under consideration for publication in any form, and it does not infringe any copyright laws. The signing author or agent further warrants that all authors, if applicable, have been informed of the terms of this agreement and obtained the approval and authority to sign the agreement.