ENRU  
Volume 22, No 5, 2015, P. 30–51 UDC 519.8
Keywords: multiobjectiveness, graph cut, Pareto set, stability radius, Hölder metric, intractability. DOI: 10.17377/daio.2015.22.477 Kirill G. Kuzmin ^{1} Received 16 February 2015 References[1] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NPCompleteness, Freeman, San Francisco, 1979. Translated under the title Vychislitel’nye mashiny i trudnoreshaemye zadachi, Mir, Moscow, 1982.[2] V. A. Emelichev and K. G. Kuzmin, Estimating the stability radius of the vector MAXCUT problem, Diskretn. Mat., 25, No. 2, 5–12, 2013. Translated in Discrete Math. Appl., 23, No. 2, 145–152, 2013. [3] V. A. Emelichev and K. G. Kuzmin, Stability analysis of the efficient solution to a vector problem of a maximum cut, Diskretn. Anal. Issled. Oper., 20, No. 4, 27–35, 2013. [4] V. A. Emelichev and D. P. Podkopaev, Stability and regularization of vector integer linear programming problems, Diskretn. Anal. Issled. Oper., Ser. 2, 8, No. 1, 47–69, 2001. [5] I. V. Kozlov, On stable instances of the MINCUT problem, Model. Anal. Inf. Sist., 21, No. 4, 54–63, 2014. [6] T. T. Lebedeva and T. I. Sergienko, Different types of stability of vector integer optimization problem: General approach, Kibern. Sist. Anal., No. 3, 142–148, 2008. Translated in Cybern. Syst. Anal., 44, No. 3, 429–433, 2008. [7] Y. Bilu, A. Daniely, N. Linial, and M. Saks, On the practically interesting instances of MAXCUT, in N. Portier and Th. Wilke, eds., Proc. 30th Int. Symp. Theor. Aspects Computer Sci., Kiel, Germany, Feb. 27 – Mar. 2, 2013, pp. 526–537, Schloss Dagstuhl–LeibnizZentrum fuer Informatik, Dagstuhl, Germany, 2013. [8] N. Chakravarti and A. P. M. Wagelmans, Calculation of stability radii for combinatorial optimization problem, Oper. Res. Lett., 23, No. 1–2, 1–7, 1998. [9] V. A. Emelichev and D. P. Podkopaev, Quantitative stability analysis for vector problems of 01 programming, Discrete Optim., 7, No. 1–2, 48–63, 2010. [10] H. J. Greenberg, An annotated bibliography for postsolution analysis in mixed integer programming and combinatorial optimization, in D. L. Woodruff, ed., Advances in Computational and Stochastic Optimization, Logic Programming and Heuristic Search, pp. 97–147, Kluwer Acad. Publ., Norwell, 1998. [11] Chr. Hohmann and W. Kern, Optimization and optimality test for the MaxCut Problem, Z. Oper. Res., 34, No. 3, 195–206, 1990. [12] J. Roland, Y. De Smet, and J. R. Figueira, On the calculation of stability radius for multiobjective combinatorial optimization problems by inverse optimization, 4OR, 10, No. 4, 379–389, 2012. [13] S. van Hoesel and A. Wagelmans, On the complexity of postoptimality analysis of 0/1 programs, Discrete Appl. Math., 91, No. 1–3, 251–263, 1999. 

© Sobolev Institute of Mathematics, 2015  