Многогранники с высокой плотностью графа и полиномиальная разрешимость задач комбинаторной оптимизации

Определяется класс многогранников, которые задаются системами линейных ограничений с полиномиальным по размерности многогранников количеством уравнений и неравенств и плотность графов которых экспоненциальна. Существование таких многогранников позволяет применять полиномиальные алгоритмы линейного программирования для задач дискретной оптимизации, труднорешаемых традиционными комбинаторными методами.