Аннотация:
Устанавливается, что многогранник $M$ любой задачи комбинаторной оптимизации с линейной целевой функцией является аффинным образом некоторой грани многогранника разрезов, размерность которого полиномиальна относительно размерности $M$.
Ключевые слова:комбинаторная оптимизация, многогранник разрезов, многогранник задачи о рюкзаке, грани, полиномиальная сводимость задач.
Полный текст:
PDF файл (197 kB)