Том 20, номер 4, 2013 г., Стр. 27-35
УДК 519.8
Емеличев В. А., Кузьмин К. Г.
Анализ устойчивости эффективного решения векторной задачи о максимальном разрезе графа
Аннотация:
Получена формула радиуса устойчивости эффективного решения векторного варианта задачи о максимальном разрезе графа (MAX-CUT problem) в случае, когда в пространстве параметров задана метрика Гёльдера.
Библиогр. 18.
Ключевые слова: многокритериальность, эффективный разрез графа, радиус устойчивости, норма Гёльдера.
Емеличев Владимир Алексеевич 1
Кузьмин Кирилл Геннадьевич 1
1. Белорусский гос. университет,
пр-т Независимости, 4, 220030 Минск, Беларусь
е-mail: emelichev@tut.by, kuzminkg@mail.ru
Статья поступила 11 октября 2012 г.
Исправленный вариант — 1 января 2013 г.
Литература
[1] Воденников А. Г., Емеличев В. А., Кузьмин К. Г. Об одном типе устойчивости векторной комбинаторной задачи размещения // Дискрет. анализ и исслед. операций. Сер. 2. - 2007. - Т. 14, № 2. - С. 32–40.
[2] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. - М.: Мир, 1982. - 416 с.
[3] Емеличев В. А., Карпук А. В., Кузьмин К. Г. О квазиустойчивости лексикографической минимаксной комбинаторной задачи с распадающимися переменными // Дискрет. анализ и исслед. операций. - 2010. - Т. 17, № 3. - С. 32–45.
[4] Емеличев В. А., Кузьмин К. Г. Анализ чувствительности эффективного решения векторной булевой задачи минимизации проекций линейных функций на R+ и R− // Дискрет. анализ и исслед. операций. Сер. 2. - 2005. - Т. 12, № 2. - С. 24–43.
[5] Емеличев В. А., Кузьмин К. Г. О радиусе устойчивости эффективного решения векторной задачи целочисленного линейного программирования в метрике Гёльдера // Кибернетика и систем. анализ. - 2006. - № 4. - С. 175–181.
[6] Емеличев В. А., Кузьмин К. Г. Об устойчивости эффективных решений многокритериальной задачи о максимальном разрезе графа // Мат. Всеукр. научн. семинара «Комбiнаторна оптимiзацiя та нечiткi множини» (КОНеМ–2011) (Полтава, Украина, 26–27 августа 2011 г.). - С. 39–41.
[7] Емеличев В. А., Кузьмин К. Г. Общий подход к исследованию устойчивости парето-оптимального решения векторной задачи целочисленного линейного программирования // Дискрет. математика. - 2007. - Т. 19, вып. 3. - С. 79–3.
[8] Емеличев В. А., Кузьмин К. Г. Постоптимальный анализ многокритериальной задачи о максимальном разрезе графа // Мат. 2-й междунар. науч.-практ. конф. «Веб-программирование и интернет технологии Web-Conf2012» (Минск, 5–7 июня 2012 г.). - С. 67.
[9] Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. 3-е изд. - М.: Либроком, 2013. - 392 с.
[10] Зыков А. А. Основы теории графов. - М.: Вуз. кн., 2004. - 663 с.
[11] Харди Г., Литтльвуд Дж. E., Полиа Г. Неравенства. - М.: ЛКИ, 2008. - 456 с.
[12] Шило В. П., Шило О. В. Решение задачи о максимальном разрезе графа методом глобального равновесного поиска // Кибернетика и систем. анализ. - 2010. - № 5. - С. 68–79.
[13] Barahona F., Grötschel M., Jünger M., Reinelt G. An application of combinatorial optimization to statistical physics and circuit layout design // Oper. Res. - 1988. - Vol. 36, N 3. - P. 493–513.
[14] Burer S., Monteiro R. D. C., Zhang Y. Rank-two relaxation heuristics for MAX-CUT and other binary quadratic programs // SIAM J. Optim. - 2001. - Vol. 12. - P. 503–521.
[15] Chang K. C., Du D. H.-C. Efficient algorithms for layer assignment problem // IEEE Trans. Computer-Aided Des. Integrated Circuits Syst. - 1987. - Vol. 6. - P. 67–78.
[16] Emelichev V., Podkopaev D. Quantitative stability analysis for vector problems of 0-1 programming // Discrete Optim. - 2010. - Vol. 7, N 1–2. - P. 48–63.
[17] Pardalos P., Prokopyev O., Shylo O., Shylo V. Global equilibrium search applied to the unconstrained binary quadratic optimization problem // Optim. Methods Softw. - 2008. - Vol. 23. - P. 129–140.
[18] Poljac S., Tuza Z. Maximum cuts and large bipartite subgraphs // DIMACS Ser. Discrete Math. Theor. Comput. Sci. - 1995. - Vol. 20. - P. 181–244.
