|
Diskretnyi Analiz i Issledovanie Operatsii, 2011, Volume 18, Issue 3, Pages 76–83
(Mi da655)
|
|
|
|
This article is cited in 4 scientific papers (total in 4 papers)
SAT polytopes are faces of polytopes of the traveling salesman problem
A. N. Maksimenko P. G. Demidov Yaroslavl State University, Yaroslavl, Russia
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.
Received: 19.07.2010 Revised: 15.03.2011
Citation:
A. N. Maksimenko, “SAT polytopes are faces of polytopes of the traveling salesman problem”, Diskretn. Anal. Issled. Oper., 18:3 (2011), 76–83
Linking options:
https://www.mathnet.ru/eng/da655 https://www.mathnet.ru/eng/da/v18/i3/p76
|
Statistics & downloads: |
Abstract page: | 495 | Full-text PDF : | 120 | References: | 56 | First page: | 4 |
|