Abstract
Under consideration is the multiobjective version of the maximum cut problem. The formulas together with the lower and upper exact bounds of stability radii are obtained for solutions of this problem as well as for the various types of stability of the problem under assumption that the Hölder metrics are given on the spaces of a disturbing parameter. It is proved that the problem of finding the radii of every type of stability is intractable unless P=NP.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979, Mir,Moscow, 1982).
V. A. Emelichev and K. G. Kuz’min, “Estimating the Stability Radius of the Vector MAX-CUT Problem,” Diskretn.Mat. 25 (2), 5–12 (2013) [DiscreteMath. Appl. 23 (2), 145–152 (2013)].
V. A. Emelichev and K. G. Kuz’min, “Stability Analysis of the Efficient Solution to a Vector Problem of aMaximumCut,” Diskretn. Anal. Issled. Oper. 20 (4), 27–35 (2013).
V. A. Emelichev and D. P. Podkopaev, “Stability and Regularization of Vector Integer Linear Programming Problems,” Diskretn. Anal. Issled. Oper. Ser. 2, 8 (1), 47–69 (2001).
I. V. Kozlov, “On Stable Instances of the MIN-CUT Problem,” Model. Anal. Inform. Sist. 21 (4), 54–63 (2014).
T. T. Lebedeva and T. I. Sergienko, “Various Types of Stability of Vector Integer Optimization Problem: General Approach,” Kibernet. Sist. Anal. No. 3, 142–148 (2008) [Cybernet. Systems Anal. 44 (3), 429–433 (2008)].
Y. Bilu, A. Daniely, N. Linial, and M. Saks, “On the Practically Interesting Instances of MAXCUT,” in Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, Kiel, Germany, February 27—March 2, 2013, Ed. by N. Portier and Th. Wilke (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2013), pp. 526–537.
N. Chakravarti and A. P. M. Wagelmans, “Calculation of Stability Radii for Combinatorial Optimization Problem,” Oper. Res. Lett. 23 (1–2), 1–7 (1998).
V. A. Emelichev and D. P. Podkopaev, “Quantitative Stability Analysis for Vector Problems of 0-1 Programming,” Discrete Optim. 7 (1–2), 48–63 (2010).
H. J. Greenberg, “An Annotated Bibliography for Post-Solution Analysis in Mixed Integer Programming and Combinatorial Optimization,” in Advances in Computational and Stochastic Optimization, Logic Programming, and Heuristic Search, Ed. by D. L. Woodruff (Kluwer Acad. Publ., Norwell, 1998), pp. 97–147.
Chr. Hohmann and W. Kern, “Optimization and Optimality Test for the Max-Cut Problem,” J. Oper. Res. 34 (3), 195–206 (1990).
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 (4), 379–389 (2012).
S. van Hoesel and A. Wagelmans, “On the Complexity of Postoptimality Analysis of 0/1 Programs,” Discrete Appl. Math. 91 (1–3), 251–263 (1999).
Author information
Authors and Affiliations
Corresponding author
Additional information
Original Russian Text © K.G. Kuz’min, 2015, published in Diskretnyi Analiz i Issledovanie Operatsii, 2015, Vol. 22, No. 5, pp. 30–49.
Rights and permissions
About this article
Cite this article
Kuz’min, K.G. A general approach to the calculation of stability radii for the max-cut problem with multiple criteria. J. Appl. Ind. Math. 9, 527–539 (2015). https://doi.org/10.1134/S1990478915040092
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S1990478915040092