Volume 22, No 5, 2015, P. 30–51
UDC 519.8
Kuzmin K. G.
A united approach to finding the stability radii in a multicriteria problem of a maximum cut
Abstract:
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 P=NP.
Bibliogr. 13.
Keywords: multi-objectiveness, graph cut, Pareto set, stability radius, Hölder metric, intractability.
DOI: 10.17377/daio.2015.22.477
Kirill G. Kuzmin 1
1. Belarusian State University
4 Nezavisimosti’ Ave., 220030 Minsk, Belarus
e-mail: kuzminkg@mail.ru
Received 16 February 2015
References
[1] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, 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 MAX-CUT 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 MIN-CUT 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–Leibniz-Zentrum 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 0-1 programming, Discrete Optim., 7, No. 1–2, 48–63, 2010.
[10] H. J. Greenberg, An annotated bibliography for post-solution 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 Max-Cut 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 multi-objective 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.
