Geodesic
A united approach to finding the stability radii in a~multicriteria problem of a~maximum cut
Diskretnyj analiz i issledovanie operacij, Tome 22 (2015) no. 5, pp. 30-51.

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

A multicriteria variant of the maximum cut problem is considered. The lower and upper achievable bounds on the radii of various types of stability are obtained assuming that the Hölder metrics are set in the parameters space. It is shown that to calculate any of the stability radii is an intractable problem unless $\mathrm{P\ne NP}$. Bibliogr. 13.
Keywords: multi-objectiveness, graph cut, Pareto set, stability radius, Hölder metric, intractability. 
@article{DA_2015_22_5_a1,
     author = {K. G. Kuzmin},
     title = {A united approach to finding the stability radii in a~multicriteria problem of a~maximum cut},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {30--51},
     publisher = {mathdoc},
     volume = {22},
     number = {5},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2015_22_5_a1/}
}
TY  - JOUR
AU  - K. G. Kuzmin
TI  - A united approach to finding the stability radii in a~multicriteria problem of a~maximum cut
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2015
SP  - 30
EP  - 51
VL  - 22
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2015_22_5_a1/
LA  - ru
ID  - DA_2015_22_5_a1
ER  - 
%0 Journal Article
%A K. G. Kuzmin
%T A united approach to finding the stability radii in a~multicriteria problem of a~maximum cut
%J Diskretnyj analiz i issledovanie operacij
%D 2015
%P 30-51
%V 22
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2015_22_5_a1/
%G ru
%F DA_2015_22_5_a1
K. G. Kuzmin. A united approach to finding the stability radii in a~multicriteria problem of a~maximum cut. Diskretnyj analiz i issledovanie operacij, Tome 22 (2015) no. 5, pp. 30-51. http://geodesic.mathdoc.fr/item/DA_2015_22_5_a1/

[1] M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979 | MR | MR | Zbl

[2] V. A. Emelichev, K. G. Kuzmin, “Estimating the stability radius of the vector MAX-CUT problem”, Discrete Math. Appl., 23:2 (2013), 145–152 | DOI | DOI | MR | Zbl

[3] V. A. Emelichev, K. G. Kuzmin, “Stability analysis of the efficient solution to a vector problem of a maximum cut”, Diskretn. Anal. Issled. Oper., 20:4 (2013), 27–35 | MR | Zbl

[4] V. A. Emelichev, D. P. Podkopaev, “Stability and regularization of vector integer linear programming problems”, Diskretn. Anal. Issled. Oper. Ser. 2, 8:1 (2001), 47–69 | MR | Zbl

[5] I. V. Kozlov, “On stable instances of the MIN-CUT problem”, Model. Anal. Inf. Sist., 21:4 (2014), 54–63

[6] T. T. Lebedeva, T. I. Sergienko, “Different types of stability of vector integer optimization problem: General approach”, Cybern. Syst. Anal., 44:3 (2008), 429–433 | DOI | MR | Zbl

[7] Bilu Y., Daniely A., Linial N., Saks M., “On the practically interesting instances of MAXCUT”, Proc. 30th Int. Symp. Theoret. Aspects Computer Sci. (Kiel, Germany, Feb. 27 – Mar. 2, 2013), eds. N. Portier, Th. Wilke, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, 2013, 526–537 | MR

[8] Chakravarti N., Wagelmans A. P. M., “Calculation of stability radii for combinatorial optimization problem”, Oper. Res. Lett., 23:1–2 (1998), 1–7 | DOI | MR | Zbl

[9] Emelichev V. A., Podkopaev D. P., “Quantitative stability analysis for vector problems of 0-1 programming”, Discrete Optim., 7:1–2 (2010), 48–63 | DOI | MR | Zbl

[10] Greenberg H. J., “An annotated bibliography for post-solution analysis in mixed integer programming and combinatorial optimization”, Advances in Computational and Stochastic Optimization, Logic Programming and Heuristic Search, ed. D. L. Woodruff, Kluwer Acad. Publ., Norwell, 1998, 97–147 | DOI | MR | Zbl

[11] Hohmann Chr., Kern W., “Optimization and optimality test for the Max-Cut problem”, Z. Oper. Res., 34:3 (1990), 195–206 | MR | Zbl

[12] Roland J., De Smet Y., Figueira J. R., “On the calculation of stability radius for multi-objective combinatorial optimization problems by inverse optimization”, 4OR, 10:4 (2012), 379–389 | DOI | MR | Zbl

[13] Van Hoesel S., Wagelmans A., “On the complexity of postoptimality analysis of 0/1 programs”, Discrete Appl. Math., 91:1–3 (1999), 251–263 | MR | Zbl