Abstract:
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.
Fulltext:
PDF file (380 kB)