О неравенствах, порождающих фасеты комбинаторных многогранников

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