Устойчивость в задаче поиска минимального разреза в графе
https://doi.org/10.18255/1818-1015-2014-4-54-63
Аннотация
Задача комбинаторной оптимизации называется устойчивой, если ее решение сохраняется при возмущении входных параметров, не превышающих некоторого порогового значения – радиуса устойчивости. В работах [1–3], в предположении об устойчивости входа, построены точные полиномиальные алгоритмы для некоторых NP-трудных задач о разрезах. В настоящей работе показано, как строить ускоренные алгоритмы для достаточно устойчивых полиномиальных задач. Подход иллюстрируется на примере известной задачи о минимальном разрезе (MINCUT). Построен O(n²) точный алгоритм решения n-устойчивой задачи MINCUT. Кроме того, построен полиномиальный алгоритм вычисления радиуса устойчивости задачи MINCUT и получен простой критерий n-устойчивости.
При поддержке: РФФИ
Об авторе
Илья Владимирович Козлов
Московский физико-технический институт
Россия
кафедра математических основ управления аспирант, ассистент, 141700, Московская облаcть, г. Долгопрудный, Институтский пер., 9
Россия
кафедра математических основ управления аспирант, ассистент, 141700, Московская облаcть, г. Долгопрудный, Институтский пер., 9
Список литературы
1. Bilu Y., Linial N. Are stable instances easy? // Innov. in Comp. Sci. 2010. P. 332–341.
2. Linial N. et.al. On the practically interesting instances of MAXCUT // STACS. 2013. P. 526–537.
3. Makarychev K., Makarychev Y., Vijayaraghavan A. Bulu-Linial stable instances of max cut and minimum multiway cut // Proc. of the 25-th ACM-SIAM Symp. on Disc. Alg. 2014. P. 890–906. DOI: 10.1137/1.9781611973402.67
4. Ford L., Fulkerson D. Maximal flow through a network // Canadian Journal of Mathematics. 1956. № 8. P. 399–404.
5. Gomory R., Hu T. Multi-terminal network flows // Journal of the Society of Industrial and Applied Mathematics. Dec.1961. P. 551–570.
6. Hao J., Orlin J. A faster algorithm for finding the minimum cut in a directed graph // Journal of Algorithms. Nov.1994. Vol. 17, № 3. P. 424–446.
7. Карзанов А.В., Тимофеев Е.А. Эффективный алгоритм нахождения всех минимальных реберных разрезов неориентированного графа // Кибернетика. 1986. № 2. С. 8–12. (English transl.: Karzanov A.V., Timofeev E.A. Efficient algorithm for finding all minimal edge cuts of a nonoriented graph // Kibernetika. 1986. № 2. P. 8–12.)
8. Поддерюгин В.Д. Алгоритм для нахождения реберной связности графа // Вопросы кибернетики. 1973. № 2. С. 136. (English transl.: Podderyugin V.D. An algorithm for finding the edge connectivity of graphs // Vopr. Kibern. 1973. № 2. P. 136.)
9. Karger D., Stein C. A new approach to the minimum cut problem // Journal of the ACM. Jul.1996. Vol. 43, № 4, P. 601–640.
10. Stoer M., Wagner F. A simple min-cut algorithm // Journal of the ACM. Jul. 1997. Vol. 44, № 4. P. 585–591.
11. Леонтьев В.К. Устойчивость задачи коммивояжера // Журн. вычисл. матем. и матем. физ. 1975. Т. 5, № 15. С. 1298–1309. [Leont’ev V.K. Ustoychivost zadachi kommivoyazhera // Zhurn. vychisl. matem. i matem. fiz. 1975. Vol. 5, № 15. S. 1298–1309 (in Russian)].
12. Гордеев Э.Н., Леонтьев В.К. Общий подход к исследованию устойчивости решений в задачах дискретной оптимизации // Журн. вычисл. матем. и матем. физ. 1996. Т. 1, № 36. С. 66–72. [Gordeev E.N., Leont’ev V.K. Obshchy podkhod k issledovaniyu ustoychivosti resheny v zadachakh diskretnoy optimizatsii // Zhurn. vychisl. matem. i matem. fiz. 1996. Vol. 1, № 36. S. 66–72. [in Russian].)
13. Orlin J. Max flows in O(nm) time, or better // STOC. 2013. P. 765–774.
14. King V., Rao S., Tarjan R. A Faster Deterministic Maximum Flow Algorithm // Journal of Algorithms. Nov.1994. Vol. 17, № 3. P. 447—474.
Рецензия
Для цитирования:
Козлов И.В. Устойчивость в задаче поиска минимального разреза в графе. Моделирование и анализ информационных систем. 2014;21(4):54-63. https://doi.org/10.18255/1818-1015-2014-4-54-63
For citation:
Kozlov I.V. On Stable Instances of MINCUT. Modeling and Analysis of Information Systems. 2014;21(4):54-63. (In Russ.) https://doi.org/10.18255/1818-1015-2014-4-54-63
Просмотров:
915
Послать статью по эл. почте 