On Stable Instances of MINCUT
https://doi.org/10.18255/1818-1015-2014-4-54-63
Abstract
A combinatorial optimization problem is called stable if its solution is preserved under perturbation of the input parameters that do not exceed a certain threshold – the stability radius. In [1–3] exact polynomial algorithms have been built for some NP-hard problems on cuts in the assumption of the entrance stability. In this paper we show how to accelerate some algorithms for sufficiently stable polynomial problems. The approach is illustrated by the well-known problem of the minimum cut (MINCUT). We built an O(n²) exact algorithm for solving n-stable instance of the MINCUT problem. Moreover, we present a polynomial algorithm for calculating the stability radius and a simple criterion for checking n-stability of the MINCUT problem.
About the Author
I. V. Kozlov
Moscow Institute of Physics and Technology
Russian Federation
кафедра математических основ управления аспирант, ассистент, Institutskiy pereulok, 9, Dolgoprudny, Moscow region, 141700, Russia
Russian Federation
кафедра математических основ управления аспирант, ассистент, Institutskiy pereulok, 9, Dolgoprudny, Moscow region, 141700, Russia
References
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.
Review
For citations:
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
Views:
916
Email this article 