Volume 18, No 3, 2011, P. 76-83
UDC 519.85
A. N. Maksimenko
Sat polytopes are faces of polytopes of the traveling salesman problem
Abstract:
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, face.
Maksimenko Aleksandr Nikolaevich 1
1. P. G. Demidov Yaroslavl State University,
144 Soyuznaia str., 150008 Yaroslavl, Russia
e-mail: maksimenko_a_n@mail.ru
