On nonintegral vertices of 3-SAT problem relaxation polytope

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

• комбинаторная оптимизация
• теория сложности
• многогранники
• граничные комплексы
• задача линейного программирования