Volume 22, No 3, 2015, P. 18-35

UDC 519.854
Gordeev E. N. 
Comparison of three approaches to studing stability of solutions to discrete optimization and computational geometry problems

Abstract:
In the 1970–1980s an approach to the analysis of the stability of solutions was proposed and studied. The approach is universal, but originally was used in discrete optimization problems. Later similar results, albeit in different terms, were published for various classes of problems. We show that both the statements of problems and the interpretation of results are close.
Bibliogr. 25.

Keywords: stability of the solution, stability radius, Boolean polynomial, matroid, geometric configuration.

DOI: 10.17377/daio.2015.22.461

Eduard N. Gordeev ¹
1. Bauman Moscow State Technical University,
5 2nd Bauman St., 105005 Moscow, Russia
е-mail: tatmigor@gmail.com

Received 10 September 2014
Revised 9 February 2015

References

[1] V. B. Alyushkevich and Yu. N. Sotskov, Stability in problems of scheduling, Izv. Akad. Nauk BSSR, Ser. Fiz.-Mat. Nauki, No. 3, 102–107, 1989.

[2] V. I. Artemenko, E. N. Gordeev, Yu. I. Zhuravlev et al., Construction of optimal programmed paths for the motion of a robotic manipulator, Kibern. Sist. Anal., No. 5, 82–104, 1996. Translated in Cybern. Syst. Anal., 32, No. 5, 672–687, 1996.

[3] V. L. Beresnev, Diskretnye zadachi razmeshcheniya i polinomy ot bulevykh peremennykh (Location Discrete Problems and Polynomials of Boolean Variables), Inst. Mat. SO RAN, Novosibirsk, 2005.

[4] M. N. Vyalyi, E. N. Gordeev, and S. P. Tarasov, On the stability of theVoronoi diagram, Zh. Vychisl. Mat. Mat. Fiz., 36, No. 3, 147–158, 1996. Translated in Comput. Math. Math. Phys., 36, No. 3, 405–414, 1996.

[5] E. N. Gordeev, Algorithms of polynomial complexity for computing the radius of stability in two classes of trajectory problems, Zh. Vychisl. Mat. Mat. Fiz., 27, No. 7, 984–992, 1987. Translated in USSR Comput. Math. Math. Phys., 27, No. 4, 14–20, 1987.

[6] E. N. Gordeev, Stability of the solution in the problem of the shortest way on a graph, Diskretn. Mat., 1, No. 3, 39–46, 1989.

[7] E. N. Gordeev, On solution stability in problems of computational geometry, in Tezisy dokladov Mezhdunarodnoi konf. “Intellektualizatsiya obrabotki informatsii” (Abstracts of Int. Conf. “Intellectualization of Information Processing”), Alushta, Ukraine, June 3–7, 1996, p. 8, Krym. Akad. Nauk, Simferopol, 1996.

[8] E. N. Gordeev, Stability analysis of the minimum spanning tree problem in the metric l1, Zh. Vychisl. Mat. Mat. Fiz., 39, No. 5, 770–778, 1999. Translated in Comput. Math. Math. Phys., 39, No. 5, 738–746, 1999.

[9] E. N. Gordeev, Stability analysis in optimization problems on matroids in the metric l1, Kibern. Sist. Anal., No. 2, 132–144, 2001. Translated in Cybern. Syst. Anal., 37, No. 2, 251–259, 2001.

[10] E. N. Gordeev, Using the stability radius of optimization problems to hiding and validation of information, Inzhenernyi Zh.: Nauka i Innovatsii, No. 11, 14–19, 2013.

[11] E. N. Gordeev and V. K. Leont’ev, A general approach to the study of the stability of solutions in discrete optimization problems, Zh. Vychisl. Mat. Mat. Fiz., 36, No. 1, 66–72, 1996. Translated in Comput. Math. Math. Phys., 36, No. 1, 53–58, 1996.

[12] M. V. Devyaterikova, A. A. Kolokolov, and N. A. Kosarev, The analysis of the stability of some integer programming algorithms with respect to the objective function, Izv. VUZ., Mat., No. 4, 23–32, 2011. Translated in Russ. Math. (Izv. VUZ), 55, No. 4, 18–25, 2011.

[13] V. A. Emelichev and V. V. Korotkov, On the stability radius of an effective solution of the vector quadratic Boolean bottleneck problem, Diskretn. Anal. Issled. Oper., 18, No. 6, 3–16, 2011.

[14] V. A. Emelichev and V. V. Korotkov, Stability analysis of a Pareto-optimal portfolio of the multicriteria investment problem with Wald maximin criteria, Diskretn. Anal. Issled. Oper., 19, No. 6, 23–36, 2012.

[15] A. A. Kolokolov and M. V. Devyaterikova, Stability analysis for L-partitions in a finite-dimensional space, Diskretn. Anal. Issled. Oper., Ser. 2, 7,No. 2, 47–53, 2000.

[16] V. K. Leont’ev, Stability in linear discrete problems, in S. V.Yablonskii, ed., Problemy kibernetiki (Problems of Cybernetics), Vol. 35, pp. 169–185, Nauka, Moscow, 1979.

[17] V. K. Leont’ev and E. N. Gordeev, Qualitative analysis of trajectory problems, Kibernetika, No. 5, 82–90, 1986.

[18] E. Cheng and W. H. Cunningham, A faster algorithm for computing thestrength of a network, Inf. Process. Lett., 49, No. 4, 209–212, 1994.

[19] W. H. Cunningham, Testing membership in matroid polyhedra, J. Comb. Theory, Ser. B, 36, 161–188, 1984.

[20] G. N. Fredericson and R. Solis-Oba, Increasing the weight of minimum spanning trees, in Proc. 7th Ann. ACM-SIAM Symp. Discrete Algorithms, Atlanta, GA, USA, Jan. 28–30, 1996, pp. 539–546, SIAM, Philadelphia, PA, USA, 1996.

[21] G. N. Fredericson and R. Solis-Oba, Efficient algorithms for robustness in matroid optimization, in Proc. 8th Ann. ACM-SIAM Symp. Discrete Algorithms, New Orleans, LA, USA, Jan. 4–7, 1997, pp. 659–668, SIAM, Philadelphia, PA, USA, 1997.

[22] G. Gallo, M. D. Grigoriadis, and R. E. Tarjan, A fast parametric maximum flow algorithm and application, SIAM J. Comput., 18, No. 1, 30–55, 1989.

[23] H. Narayanan, A rounding technique for the polymatroid problem, Linear Algebra Appl., 221, 41–57, 1995.

[24] Yu. N. Sotskov, V. K. Leont’ev, and E. N. Gordeev, Some concepts of stability analysis in combinatorial optimization, Discrete Appl. Math., 58,169–190, 1985.

[25] R. E. Tarjan, Sensitivity analysis of minimum spanning trees and shortest paths trees, Inf. Process. Lett., 14, No. 1, 30–33, 1982.