Том 22, номер 5, 2015 г., Стр. 30-51
УДК 519.8
Кузьмин К. Г.
Единый подход к нахождению радиусов устойчивости в многокритериальной задаче о максимальном разрезе графа
Аннотация:
Рассматривается многокритериальный вариант задачи о максимальном разрезе графа. Получены формулы и достижимые оценки радиусов устойчивости решений этой задачи, а также различных типов устойчивости самой задачи в случае, когда в пространствах возмущаемых параметров заданы метрики Гёльдера. Доказано, что задача нахождения радиусов любых типов устойчивости является труднорешаемой при P≠NP.
Библиогр. 13.
Ключевые слова: многокритериальность, разрез графа, множество Парето, радиус устойчивости, метрика Гёльдера, труднорешаемость.
DOI: 10.17377/daio.2015.22.477
Кузьмин Кирилл Геннадьевич 1
1. Белорусский гос. университет,
пр. Независимости, 4, 220030 Минск, Беларусь
e-mail: kuzminkg@mail.ru
Статья поступила 16 февраля 2015 г.
Литература
[1] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 с.
[2] Емеличев В. А., Кузьмин К. Г. Оценки радиуса устойчивости векторной задачи о максимальном разрезе графа // Дискрет. математика. 2013. Т. 25, вып. 2. С. 5–12.
[3] Емеличев В. А., Кузьмин К. Г. Анализ устойчивости эффективного решения векторной задачи о максимальном разрезе графа // Дискрет. анализ и исслед. операций. 2013. Т. 20, № 4. С. 27–35.
[4] Емеличев В. А., Подкопаев Д. П. Устойчивость и регуляризация векторных задач целочисленного линейного программирования // Дискрет. анализ и исслед. операций. Сер. 2. 2001. Т. 8, № 1. С. 47–69.
[5] Козлов И. В. Устойчивость в задаче поиска минимального разреза в графе // Моделирование и анализ информ. систем. 2014. Т. 21, № 4. С. 54–63.
[6] Лебедева Т. Т., Сергиенко Т. И. Разные типы устойчивости векторной задачи целочисленной оптимизации: общий подход // Кибернетика и систем. анализ. 2008. № 3. С. 142–148.
[7] Bilu Y., Daniely A., Linial N., Saks M. On the practically interesting instances of MAXCUT // Proc. 30th Int. Symp. Theoret. Aspects Computer Sci. (Kiel, Germany, Feb. 27 – Mar. 2, 2013). Dagstuhl: Schloss Dagstuhl–Leibniz-Zentrum fЁur Informatik, 2013. P. 526–537.
[8] Chakravarti N., Wagelmans A. P. M. Calculation of stability radii for combinatorial optimization problem // Oper. Res. Lett. 1998. Vol. 23, No. 1–2. P. 1–7.
[9] Emelichev V. A., Podkopaev D. P. Quantitative stability analysis for vector problems of 0-1 programming // Discrete Optim. 2010. Vol. 7, No. 1–2. P. 48–63.
[10] Greenberg H. J. An annotated bibliography for post-solution analysis in mixed integer programming and combinatorial optimization // Advances in Computational and Stochastic Optimization, Logic Programming and Heuristic Search. Norwell: Kluwer Acad. Publ., 1998. P. 97–147.
[11] Hohmann Chr., Kern W. Optimization and optimality test for the MaxCut problem // Z. Oper. Res. 1990. Vol. 34, No. 3. P. 195–206.
[12] Roland J., De Smet Y., Figueira J. R. On the calculation of stability radius for multi-objective combinatorial optimization problems by inverse optimization // 4OR. 2012. Vol. 10, No. 4. P. 379–389.
[13] Van Hoesel S.,Wagelmans A. On the complexity of postoptimality analysis of 0/1 programs // Discrete Appl. Math. 1999. Vol. 91, No. 1–3. P. 251–263.
