Geodesic
On nonintegral vertices of 3-SAT problem relaxation polytope
Modelirovanie i analiz informacionnyh sistem, Tome 17 (2010) no. 2, pp. 99-111.

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

New facts characterizing the vertex set of 3-SAT problem relaxation polytope are established. In particular, the question of preservation of nonintegral vertices under additional linear constraints of stronger relaxations is examined.
Keywords: combinatorial optimization, computational complexity theory, polytopes, face lattice, linear programming. 
@article{MAIS_2010_17_2_a5,
     author = {A. V. Nikolaev},
     title = {On nonintegral vertices of {3-SAT} problem relaxation polytope},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {99--111},
     publisher = {mathdoc},
     volume = {17},
     number = {2},
     year = {2010},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2010_17_2_a5/}
}
TY  - JOUR
AU  - A. V. Nikolaev
TI  - On nonintegral vertices of 3-SAT problem relaxation polytope
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2010
SP  - 99
EP  - 111
VL  - 17
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2010_17_2_a5/
LA  - ru
ID  - MAIS_2010_17_2_a5
ER  - 
%0 Journal Article
%A A. V. Nikolaev
%T On nonintegral vertices of 3-SAT problem relaxation polytope
%J Modelirovanie i analiz informacionnyh sistem
%D 2010
%P 99-111
%V 17
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2010_17_2_a5/
%G ru
%F MAIS_2010_17_2_a5
A. V. Nikolaev. On nonintegral vertices of 3-SAT problem relaxation polytope. Modelirovanie i analiz informacionnyh sistem, Tome 17 (2010) no. 2, pp. 99-111. http://geodesic.mathdoc.fr/item/MAIS_2010_17_2_a5/

[1] G. B. Dantzig, R. Fulkerson, S. M. Johnson, “Solution of a large-scale traveling salesman problem”, Operations Research, 2 (1954), 393–410 | DOI | MR

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

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

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

[5] V. A. Bondarenko , B. V. Uryvaev, “Ob odnoi zadache tselochislennoi optimizatsii”, Avtomatika i telemekhanika, 2007, no. 6, 18–23 | MR | Zbl

[6] V. A. Bondarenko, “Ob odnom kombinatornom mnogogrannike”, Modelirovanie i analiz vychislitelnykh sistem, Sb. nauch. tr., Yarosl. gos. un-t, Yaroslavl, 1987, 133–134 | MR

[7] M. V. Padberg, “The Boolean quadratic polytope: some characteristics, facets and relatives”, Mathematical Program., 45 (1989), 139–172 | DOI | MR | Zbl

[8] O. A. Dunaeva, A. V. Nikolaev, “Nekotorye svoistva relaksatsionnogo mnogogrannika zadachi 3-vypolnimost”, Trudy pyatoi Vserossiiskoi nauchnoi konferentsii s mezhdunarodnym uchastiem, Matematicheskoe modelirovanie i kraevye zadachi, SamGTU, Samara, 2008, 37–43

[9] Thomas Christof, Andreas Loebel, PORTA: POlyhedron Representation Transformation Algorithm 1.4.0, The Konrad-Zuse-Zentrum fur Informationstechnik Berlin, http://www.zib.de/Optimization/Software/Porta/