Geodesic
Construction of a relaxation of the polytope of the symmetric traveling salesman problem on the basis of a well-solvable Kalmanson case
Diskretnyj analiz i issledovanie operacij, Tome 11 (2004) no. 2, pp. 3-24.

Voir la notice de l'article provenant de la source Math-Net.Ru

@article{DA_2004_11_2_a0,
     author = {V. M. Demidenko},
     title = {Construction of a relaxation of the polytope of the symmetric traveling salesman problem on the basis of a well-solvable {Kalmanson} case},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {3--24},
     publisher = {mathdoc},
     volume = {11},
     number = {2},
     year = {2004},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2004_11_2_a0/}
}
TY  - JOUR
AU  - V. M. Demidenko
TI  - Construction of a relaxation of the polytope of the symmetric traveling salesman problem on the basis of a well-solvable Kalmanson case
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2004
SP  - 3
EP  - 24
VL  - 11
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2004_11_2_a0/
LA  - ru
ID  - DA_2004_11_2_a0
ER  - 
%0 Journal Article
%A V. M. Demidenko
%T Construction of a relaxation of the polytope of the symmetric traveling salesman problem on the basis of a well-solvable Kalmanson case
%J Diskretnyj analiz i issledovanie operacij
%D 2004
%P 3-24
%V 11
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2004_11_2_a0/
%G ru
%F DA_2004_11_2_a0
V. M. Demidenko. Construction of a relaxation of the polytope of the symmetric traveling salesman problem on the basis of a well-solvable Kalmanson case. Diskretnyj analiz i issledovanie operacij, Tome 11 (2004) no. 2, pp. 3-24. http://geodesic.mathdoc.fr/item/DA_2004_11_2_a0/

[1] Burkard R. E., Demidenko V. M., Rudolf R., “Obobschennye usloviya Supnika i Kalmansona i ikh primenenie k simmetricheskoi i nesimmetricheskoi zadache o kommivoyazhere”, Vestsi Akademii navuk Belarusi. Ser. fiz.-mat. navuk, 1996, no. 3, 69–74 | MR | Zbl

[2] Demidenko V. M., “Spetsialnye sluchai zadachi o brodyachem torgovtse s simmetricheskoi matritsei”, Dokl. AN BSSR, 24:2 (1980), 105–108 | MR | Zbl

[3] Demidenko V. M., “Obobschenie uslovii Supnika na nesimmetricheskii sluchai”, Tr. In-ta matematiki NAN Belarusi, 3, Minsk, 1999, 141–148 | MR | Zbl

[4] Demidenko V. M., “Opisanie konusa matrits Kalmansona v prostranstve minimalnoi razmernosti”, Vestsi Natsyyanalnai Akademii navuk Belarusi. Ser. fiz.-mat. navuk, 2000, no. 3, 116–122 | MR

[5] Emelichev V. A., Kovalev M. M., Kravtsov M. K., Mnogogranniki, grafy, optimizatsiya, Nauka, M., 1981 | MR

[6] Suprunenko D. A., Gruppy podstanovok, Navuka i tekhnika, Minsk, 1996

[7] Skhreiver A., Teoriya lineinogo i tselochislennogo programmirovaniya v dvukh tomakh, T. 1; Mir, M., 1991

[8] Chernikov S. N., Lineinye neravenstva, Nauka, M., 1968 | MR | Zbl

[9] Burkard R. E., Deĭneko V. G., van Dal R., van der Veen J. A. A., Woeginger G. J., “Well-solvable special cases of the TSP: a survey”, SIAM Rev., 40:3 (1998), 496–546 | DOI | MR | Zbl

[10] Burkard R. E., Demidenko V. M., Rudolf R., “A general approach for identifying special cases of the traveling salesman problem with a fixed optimal tour”, OR Transactions of China, 1:1 (1997), 41–53

[11] Burkard R. E., Klinz B., Rudolf R., “Perspectives of Monge properties in optimization”, Discrete Appl. Math., 70:2 (1996), 95–161 | DOI | MR | Zbl

[12] Dantzig G. B., Fulkerson D. R., Johnson S. M., “Solution of a large-scale traveling-salesman problem”, J. Operations Res. Soc. Amer., 2 (1954), 393–410 | MR

[13] Deǐneko V. G., Rudolf R., Woeginger G. J., Sometimes traveling is easy: the master tour problem, Report, 15, Institute of Mathematics. Techn. Univ. Graz, Graz, 1994

[14] Demidenko V. M., “An extension of Supnick conditions for the asymmetric traveling salesman problem and its application”, ECCO VIII, Abstractes, Poznan, 1995, 26

[15] Demidenko V. M., Kanonische Beschreibung des Kegels von Mongeschen Matrizen, Preprint Akademie der Wissenschaften von Belarus No 7(519), Institut für Mathematik, Minsk, 1996

[16] Demidenko V. M., Rudolf R., “A note on Kalmanson matrices”, Optimization, 40:3 (1997), 285–294 | DOI | MR | Zbl

[17] Guy R., Hanani H., Sauer N., Schonheim J., Combinatorial structures and their applications, Gordon and Breach, New York, 1970 | MR | Zbl

[18] Grötschel M., “The monotone 2-matching polytope on a complete graph”, Oper. Res. Verfahren, 24 (1977), 77–84 | MR

[19] Grötschel M., “On the monotone symmetric travelling salesman problem: hypohamiltonian/hypotraceable graphs and facets”, Math. Oper. Res., 5:2 (1980), 285–292 | DOI | MR | Zbl

[20] Grötschel M., Pulleyblank W. R., “Clique tree inequalities and the symmetric travelling salesman problem”, Math. Oper. Res., 11:4 (1986), 537–569 | DOI | MR | Zbl

[21] Gutin G., Punnen A. P., The traveling salesman problem and its variations, Kluwer Academic Publishers, Dordrecht, 2002 | MR

[22] Held M., Karp R. M., “The traveling-salesman problem and minimum spanning trees”, Oper. Res., 18:6 (1970), 1138–1162 | DOI | MR | Zbl

[23] Held M., Karp R. M., “The traveling-salesman problem and minimum spanning trees: part II”, Math. Programming, 1:1 (1971), 6–25 | DOI | MR | Zbl

[24] Kalmancon K., “Edgeconvex circuits and the traveling salesman problem”, Canad. J. Math., 27:5 (1975), 1000–1010 | MR

[25] Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G., Shmoys D. B., The traveling salesman problem, Wiley, Chichester, 1985 | MR | Zbl

[26] Papadimitriou C. H., “The adjacency relation on the traveling salesman polytope is NP-complelte”, Math. Programming, 14:3 (1978), 312–324 | DOI | MR | Zbl

[27] Papadimitriou C. H., Yannakakis M., “The complexity of facets (and some facets of on the complexity)”, J. Comput. System Sci., 28:2 (1984), 244–259 | DOI | MR | Zbl

[28] Supnick F., “Extreme Hamiltonian lines”, Annals of Math., 66 (1957), 179–201 | DOI | MR | Zbl