Р. Ю. Симанчёв, И. В. Уразова, “О гранях многогранника задачи аппроксимации графа”, Дискретн. анализ и исслед. опер., 2015, том 22, выпуск 2,страницы 86

Эта публикация цитируется в 4 статьях

О гранях многогранника задачи аппроксимации графа

Р. Ю. Симанчёв^ab, И. В. Уразова^a

^a Омский гос. университет им. Ф. М. Достоевского, пр. Мира, 55-а, 644077 Омск, Россия
^b Омский научный центр СО РАН, пр. К. Маркса, 15/1, 644024 Омск, Россия

Аннотация: Изучается многогранник задачи аппроксимации графа. Построена полиэдральная релаксация этого многогранника, описан класс опорных неравенств, в котором выделены неравенства, порождающие фасеты многогранника. Ил. 1, библиогр. 9.

Ключевые слова: $M$-граф, многогранник, полиэдр, опорное неравенство, фасета.

УДК: 519.1

Статья поступила: 11.12.2014
Переработанный вариант: 31.01.2015

DOI: 10.17377/daio.2015.22.469