Аннотация:
Устанавливаются новые факты, характеризующие множество вершин релаксационного многогранника задачи 3-ВЫПОЛНИМОСТЬ. В частности, рассмотрен вопрос о сохранении нецелочисленных вершин при переходе к более сильным релаксациям.
Ключевые слова:комбинаторная оптимизация, теория сложности, многогранники, граничные комплексы, задача линейного программирования.
Полный текст:
PDF файл (380 kB)