Geodesic
SAT polytopes are faces of polytopes of the traveling salesman problem
Diskretnyj analiz i issledovanie operacij, Tome 18 (2011) no. 3, pp. 76-83.

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

Let $U=\{u_1,u_2,\dots,u_d\}$ be a set of boolean variables and $C$ be a boolean formula over $U$ in conjunctive normal form. Denote by $Y$ the set of characteristic vectors of all satisfying truth assignments for $C$. The SAT polytope, denoted by $S(U,C)$, is the convex hull of $Y$. Denote by $T_n$ the asymmetric traveling salesman polytope. We show that $S(U,C)$ is a face of $T_n$, for $n=|U|+2\operatorname{len}(C)$, and $\operatorname{len}(C)$ is the size of the formula $C$. Ill. 1, Bibliogr. 9.
Keywords: TSP polytope, SAT polytope
Mots-clés : face. 
@article{DA_2011_18_3_a6,
     author = {A. N. Maksimenko},
     title = {SAT polytopes are faces of polytopes of the traveling salesman problem},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {76--83},
     publisher = {mathdoc},
     volume = {18},
     number = {3},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2011_18_3_a6/}
}
TY  - JOUR
AU  - A. N. Maksimenko
TI  - SAT polytopes are faces of polytopes of the traveling salesman problem
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2011
SP  - 76
EP  - 83
VL  - 18
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2011_18_3_a6/
LA  - ru
ID  - DA_2011_18_3_a6
ER  - 
%0 Journal Article
%A A. N. Maksimenko
%T SAT polytopes are faces of polytopes of the traveling salesman problem
%J Diskretnyj analiz i issledovanie operacij
%D 2011
%P 76-83
%V 18
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2011_18_3_a6/
%G ru
%F DA_2011_18_3_a6
A. N. Maksimenko. SAT polytopes are faces of polytopes of the traveling salesman problem. Diskretnyj analiz i issledovanie operacij, Tome 18 (2011) no. 3, pp. 76-83. http://geodesic.mathdoc.fr/item/DA_2011_18_3_a6/

[1] Bondarenko V. A., “Nepolinomialnaya nizhnyaya otsenka slozhnosti zadachi kommivoyazhëra v odnom klasse algoritmov”, Avtomatika i telemekhanika, 1983, no. 9, 45–50 | MR | Zbl

[2] Bondarenko V. A., Maksimenko A. N., Geometricheskie konstruktsii i slozhnost v kombinatornoi optimizatsii, LKI, M., 2008, 184 pp.

[3] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982, 416 pp. | MR

[4] Deza M. M., Loran M., Geometriya razrezov i metrik, MTsNMO, M., 2001, 736 pp.

[5] Applegate D. L., Bixby R. E., Chvatal V., Cook W. J., The traveling salesman problem: a computational study, Princeton Univ. Press, Princeton, 2006, 606 pp. | MR | Zbl

[6] Billera L. J., Sarangarajan A., “All 0-1 polytopes are travelling salesman polytopes”, Combinatorica, 16 (1996), 175–188 | DOI | MR | Zbl

[7] Fiorini S., “A combinatorial study of partial order polytopes”, Eur. J. Comb., 24:2 (2003), 149–159 | DOI | MR | Zbl

[8] Karp R. M., Papadimitriou C. H., “On linear characterizations of combinatorial optimization problems”, SIAM J. Computing, 11:4 (1982), 620–632 | DOI | MR | Zbl

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