Geodesic
Comparison of three approaches to studing stability of solutions to discrete optimization and computational geometry problems
Diskretnyj analiz i issledovanie operacij, Tome 22 (2015) no. 3, pp. 18-35.

Voir la notice de l'article provenant de la source Math-Net.Ru

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, matroid, geometric configuration.
Mots-clés : Boolean polynomial 
@article{DA_2015_22_3_a1,
     author = {E. N. Gordeev},
     title = {Comparison of three approaches to studing stability of solutions to discrete optimization and computational geometry problems},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {18--35},
     publisher = {mathdoc},
     volume = {22},
     number = {3},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2015_22_3_a1/}
}
TY  - JOUR
AU  - E. N. Gordeev
TI  - Comparison of three approaches to studing stability of solutions to discrete optimization and computational geometry problems
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2015
SP  - 18
EP  - 35
VL  - 22
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2015_22_3_a1/
LA  - ru
ID  - DA_2015_22_3_a1
ER  - 
%0 Journal Article
%A E. N. Gordeev
%T Comparison of three approaches to studing stability of solutions to discrete optimization and computational geometry problems
%J Diskretnyj analiz i issledovanie operacij
%D 2015
%P 18-35
%V 22
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2015_22_3_a1/
%G ru
%F DA_2015_22_3_a1
E. N. Gordeev. Comparison of three approaches to studing stability of solutions to discrete optimization and computational geometry problems. Diskretnyj analiz i issledovanie operacij, Tome 22 (2015) no. 3, pp. 18-35. http://geodesic.mathdoc.fr/item/DA_2015_22_3_a1/

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

[2] V. I. Artemenko, E. N. Gordeev, Yu. I. Zhuravlev et al., “Construction of optimal programmed paths for the motion of a robotic manipulator”, Cybern. Syst. Anal., 32:5 (1996), 672–687 | DOI | MR | Zbl

[3] V. L. Beresnev, Location Discrete Problems and Polynomials of Boolean Variables, Inst. Mat. SO RAN, Novosibirsk, 2005

[4] M. N. Vyalyi, E. N. Gordeev, S. P. Tarasov, “On the stability of the Voronoi diagram”, Comput. Math. Math. Phys., 36:3 (1996), 405–414 | MR | Zbl

[5] E. N. Gordeev, “Algorithms of polynomial complexity for computing the radius of stability in two classes of trajectory problems”, USSR Comput. Math. Math. Phys., 27:4 (1987), 14–20 | DOI | MR | Zbl | Zbl

[6] E. N. Gordeev, “Stability of the solution in the problem of the shortest way on a graph”, Diskretn. Mat., 1:3 (1989), 39–46 | MR | Zbl

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

[8] E. N. Gordeev, “Stability analysis of the minimum spanning tree problem in the metric $l_1$”, Comput. Math. Math. Phys., 39:5 (1999), 738–746 | MR | Zbl

[9] E. N. Gordeev, “Stability analysis in optimization problems on matroids in the metric $l_1$”, Cybern. Syst. Anal., 37:2 (2001), 251–259 | DOI | MR | Zbl

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

[11] E. N. Gordeev, V. K. Leont'ev, “A general approach to the study of the stability of solutions in discrete optimization problems”, Comput. Math. Math. Phys., 36:1 (1996), 53–58 | MR | Zbl

[12] M. V. Devyaterikova, A. A. Kolokolov, N. A. Kosarev, “The analysis of the stability of some integer programming algorithms with respect to the objective function”, Russ. Math. (Izv. VUZ), 55:4 (2011), 18–25 | DOI | MR | Zbl

[13] V. A. Emelichev, V. V. Korotkov, “On the stability radius of an effective solution of the vector quadratic Boolean bottleneck problem”, Diskretn. Anal. Issled. Oper., 18:6 (2011), 3–16 | MR | Zbl

[14] V. A. Emelichev, V. V. Korotkov, “Stability analysis of a Pareto-optimal portfolio of the multicriteria investment problem with Wald maximin criteria”, Diskretn. Anal. Issled. Oper., 19:6 (2012), 23–36 | MR | Zbl

[15] A. A. Kolokolov, M. V. Devyaterikova, “Stability analysis for $L$-partitions in a finite-dimensional space”, Diskretn. Anal. Issled. Oper., Ser. 2, 7:2 (2000), 47–53 | MR | Zbl

[16] V. K. Leont'ev, “Stability in linear discrete problems”, Problems of Cybernetics, 35, ed. S. V. Yablonskii, Nauka, Moscow, 1979, 169–185 | MR

[17] V. K. Leont'ev, E. N. Gordeev, “Qualitative analysis of trajectory problems”, Kibernetika, 1986, no. 5, 82–90 | MR

[18] Cheng E., Cunningham W. H., “A faster algorithm for computing the strength of a network”, Inf. Process. Lett., 49 (1994), 209–212 | DOI | Zbl

[19] Cunningham W. H., “Testing membership in matroid polyhedra”, J. Comb. Theory. Ser. B, 36 (1984), 161–188 | DOI | MR | Zbl

[20] Fredericson G. N., Solis-Oba R., “Increasing the weight of minimum spanning trees”, Proc. 7th Ann. ACM-SIAM Symp. Discrete Algorithms, SIAM, Philadelphia, PA, 1996, 539–546 | MR

[21] Fredericson G. N., Solis-Oba R., “Efficient algorithms for robustness in matroid optimization”, Proc. 8th Ann. ACM-SIAM Symp. Discrete Algorithms, SIAM, Philadelphia, PA, 1997, 659–668 | MR

[22] Gallo G., Grigoriadis M. D., Tarjan R. E., “A fast parametric maximum flow algorithm and application”, SIAM J. Comput., 18:1 (1989), 30–55 | DOI | MR | Zbl

[23] Narayanan H., “A rounding technique for the polymatroid problem”, Linear Algebra Appl., 221 (1995), 41–57 | DOI | MR | Zbl

[24] Sotskov Yu. N., Leont'ev V. K., Gordeev E. N., “Some concepts of stability analysis in combinatorial optimization”, Discrete Appl. Math., 58 (1985), 169–190 | DOI | MR

[25] Tarjan R. E., “Sensitivity analysis of minimum spanning trees and shortest paths trees”, Inf. Process. Lett., 14:1 (1982), 30–33 | DOI | MR