On the skeleton of the polytope of pyramidal tours

V. A. Bondarenko ; A. V. Nikolaev

Diskretnyj analiz i issledovanie operacij, Tome 25 (2018) no. 1, pp. 5-24.

Résumé

We consider the skeleton of the polytope of pyramidal tours. A Hamiltonian tour is called pyramidal if the salesperson starts in city $1$, then visits some cities in increasing order of their numbers, reaches city $n$, and returns to city $1$ visiting the remaining cities in decreasing order. The polytope $\mathrm{PYR}(n)$ is defined as the convex hull of the characteristic vectors of all pyramidal tours in the complete graph $K_n$. The skeleton of $\mathrm{PYR}(n)$ is the graph whose vertex set is the vertex set of $\mathrm{PYR}(n)$ and the edge set is the set of geometric edges or one-dimensional faces of $\mathrm{PYR}(n)$. We describe the necessary and sufficient condition for the adjacency of vertices of the polytope $\mathrm{PYR}(n)$. On this basis we developed an algorithm to check the vertex adjacency with linear complexity. We establish that the diameter of the skeleton of $\mathrm{PYR}(n)$ equals $2$, and the asymptotically exact estimate of the clique number of the skeleton of $\mathrm{PYR}(n)$ is $\mathrm{\Theta }(n^2)$. It is known that this value characterizes the time complexity in a broad class of algorithms based on linear comparisons. Illustr. 4, bibliogr. 23.

Détail

Mots-clés : pyramidal tour, $1$-skeleton, necessary and sufficient condition of adjacency, clique number, graph diameter.

Bibliographie

[1] V. S. Aizenshtat, D. N. Kravchuk, “On the minimum of a linear form on the set of all cycles of the symmetric group $S_n$”, Cybern., 4 (1968), 52–53 | DOI | MR

[2] Yu. A. Belov, “On clique number of the matroid graph”, Operations Research Models in Computing Systems, Yarosl. Gos. Univ., Yaroslavl, 1985, 95–100 (Russian)

[3] V. A. Bondarenko, “Nonpolynomial lower bounds for the complexity of the traveling salesman problem in a class of algorithms”, Autom. Remote Control, 44:9 (1983), 1137–1142 | MR | Zbl

[4] V. A. Bondarenko, A. N. Maksimenko, Geometric constructions and complexity in combinatorial optimization, LKI, Moscow, 2008 (Russian)

[5] V. A. Bondarenko, A. V. Nikolaev, D. A. Shovgenov, “1-skeletons of the spanning tree problems with additional constraints,”, Model. Anal. Inf. Syst., 22:9 (2015), 453–463 (Russian) | DOI | MR

[6] P. S. Klyaus, Generation of testproblems for the traveling salesman problem, Prepr. No. 16, Inst. Mat. AN BSSR, Minsk, 1976 (Russian)

[7] Applegate D. L., Bixby R. E., Chvátal V., Cook W. J., The traveling salesman problem: a computational study, Princeton Univ. Press, Princeton, NJ, 2007, 608 pp. | MR

[8] Bondarenko V. A., Nikolaev A. V., “On graphs of the cone decompositions for the min-cut and max-cut problems”, Int. J. Math. Math. Sci., 2016 (2016), 1–6 | DOI | MR

[9] Bondarenko V. A., Nikolaev A. V., “On the skeleton of the pyramidal tours polytope/”, Abstr. 17th Baikal Int. School–Seminar “Methods of Optimization and Their Applications”, ESI SB RAS, Irkutsk, 2017, 84

[10] Bondarenko V. A., Nikolaev A. V., “Some properties of the skeleton of the pyramidal tours polytope”, Electron. Notes Discrete Math., 61 (2017), 131–137 | DOI

[11] Burkard R. E., Deineko V. G., Van Dal R., Van der Veen J. A. A., Woeginger G. J., “Well-solvable special cases of the traveling salesman problem: a survey”, SIAM Rev., 40:3 (1998), 496–546 | DOI | MR

[12] Dantzig G., Fulkerson R., Johnson S., Solution of a large scale traveling salesman problem, Tech. Rep. P-510, RAND Corp., Santa Monica, CA, 1954 | MR

[13] Deineko V. G., Klinz B., Tiskin A., Woeginger G. J., “Four-point conditions for the TSP: the complete complexity classification”, Discrete Optim., 14 (2014), 147–159 | DOI | MR

[14] Geist D., Rodin E. Y., “Adjacency of the $0$–$1$ knapsack problem”, Comput. Oper. Res., 19:8 (1992), 797–800 | DOI | MR

[15] Gilmore P. C., Lawler E. L., Shmoys D. B., “Well-solved special cases”, The traveling salesman problem: a guided tour of combinatorial optimization, Wiley, Chichester, 1985, 87–143 | MR

[16] Girlich E., Höding M., Horbach A., Kovalev M., “On the facets and diameter of the $k$-cycle polytope”, Optimization, 55:4 (2006), 311–339 | DOI | MR

[17] Grötschel M., Padberg M., “Polyhedral theory”, The traveling salesman problem: a guided tour of combinatorial optimization, Wiley, Chichester, 1985, 251–305 | MR

[18] Padberg M. W., Rao M. R., “The travelling salesman problem and a class of polyhedra of diameter two”, Math. Program., 7:1 (1974), 32–45 | DOI | MR

[19] Papadimitriou C. H., “The adjacency relation on the traveling salesman polytope is NP-complete”, Math. Program., 14:1 (1978), 312–324 | DOI | MR

[20] Rispoli F. J., Cosares S., “A bound of $4$ for the diameter of the symmetric traveling salesman polytope”, SIAM J. Discrete Math., 11:3 (1998), 373–380 | DOI | MR

[21] Sierksma G., “The skeleton of the symmetric traveling salesman polytope”, Discrete Appl. Math., 43:1 (1993), 63–74 | DOI | MR

[22] Sierksma G., Teunter R. H., Tijssen G. A., “Faces of diameter two on the Hamiltonian cycle polytype”, Oper. Res. Lett., 18:2 (1995), 59–64 | DOI | MR

[23] Sierksma G., Tijssen G. A., “Faces with large diameter on the symmetric traveling salesman polytope”, Oper. Res. Lett., 12:2 (1992), 73–77 | DOI | MR