Optimal Ordering of Conflicting Objects and the Traveling Salesman Problem
Abstract
The paper presents the setting of the problem of optimal ordering of conflicting objects related to the Travelling Salesman Problem (TSP). The problem of optimal ordering of conflicting objects appears in sociology, in graph analysis and finding in them optimal paths, in advertising in various media. Solution algorithms are described for this and related problems. The TSP with sparse matrix is also considered. For sparse practice cases of the TSP necessary and sufficient conditions are proved to objective function attained its minimum and the algorithms guaranteeing exact solution are constructed. The practical results of analytical and numerical investigations of algorithm complexity and solution accuracy are presented as well as recommendations for the algorithm applications to the solution of these problems.
About the Authors
Alexey Voevodin
Business Center «Video International», Moscow
Russian Federation
Russian Federation
Semen Kosyachenko
Business Center «Video International», Moscow
Russian Federation
Russian Federation
References
1. Kuzyurin N.N., Fomin S.А. Effektivnye algoritmy i slozhnost' vychislenij [Efficient algorithms and computational complexity]. Uchebnoe posobie [Tutorial]. Moscow, MIPT’ Publ., 2007. 312 с.
2. http://en.wikipedia.org/wiki/Travelling_salesman_problem
3. Peter Komjach: http://mathoverflow.net/questions/30270/maximum-number-of-mutually-equidistant-points-in-an-n-dimensional-euclidean-spac, geometry - Maximum number of mutually equidistant points in an n-dimensional Euclidean space is (n+1)_ Proof – MathOverflow, answered Jul 2, 2010.
4. Alan George, Joseph W. H. Liu. Computer Solution of Large Sparse Positive Definite Systems. Prentice-Hall, Inc., Englewood Cliffs, N.J. 1981 – 324 pages.
5. Sergio Pissanetzky. Sparse Matrix Technology. Academic Press, 1984 – 321 pages.
6. Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. 2009 [1990].
Review
For citations:
Voevodin A., Kosyachenko S. Optimal Ordering of Conflicting Objects and the Traveling Salesman Problem. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2013;25:207-224. (In Russ.)
Email this article 