Том 22, номер 2, 2015 г., Стр. 86−101

УДК 519.1
Р. Ю. Симанчёв, И. В. Уразова
О гранях многогранника задачи аппроксимации графа

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

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

DOI: 10.17377/daio.2015.22.469

Симанчёв Руслан Юрьевич ^1,2
Уразова Инна Владимировна ¹
1. Омский гос. университет им. Ф. М. Достоевского
пр. Мира, 55–а, 644077 Омск, Россия
2. Омский научный центр СО РАН
пр. К. Маркса, 15/1, 644024 Омск, Россия
е-mail: osiman@rambler.ru, urazovainn@mail.ru

Статья поступила 11 декабря 2014 г.
Исправленный вариант — 31 января 2015 г.

Литература

[1] Емеличев В. А., Ковалев М. М., Кравцов М. К. Многогранники. Графы. Оптимизация. М.: Наука, 1981. 344 с.

[2] Ильев В. П., Ильева С. Д., Навроцкая А. А. Приближённые алгоритмы для задач аппроксимации графов // Дискрет. анализ и исслед. операций. 2011. Т. 18, № 1. С. 41–60.

[3] Ильев В. П., Фридман Г. Ш. К задаче аппроксимации графами с фиксированным числом компонент // Докл. АН СССР. 1982. Т. 264, № 3. С. 533–538.

[4] Селиверстов А. В. Многогранники и связные подграфы // Дискрет. анализ и исслед. операций. 2014. Т. 21, № 3. С. 82–86.

[5] Симанчёв Р. Ю., Шерешик Н. Ю. Целочисленные модели обслуживания требований одним прибором с прерываниями // Дискрет. анализ и исслед. операций. 2014. Т. 21, № 4. С. 89–101.

[6] Схрейвер А. Теория линейного и целочисленного программирования. Т. 2. М.: Мир, 1991. 342 с.

[7] Фридман Г. Ш. Одна задача аппроксимации графов // Управляемые системы. 1971. Вып. 8. C. 73–75.

[8] Grotschel M., Holland O. Solution of large-scale symmetric travelling salesman problems // Math. Programming. 1991. Vol. 51, No. 2. P. 141–202.

[9] Shamir R., Sharan R., Tsur D. Cluster graph modification problems // Discrete Appl. Math. 2004. Vol. 144, No. 1–2. P. 173–182.