On the complexity of calculating sensitivity parameters in Boolean programming problems. (English. Russian original) Zbl 1330.90054
Cybern. Syst. Anal. 51, No. 5, 714-719 (2015); translation from Kibern. Sist. Anal. 2015, No. 2, 56-62 (2015).
Summary: This article shows that, for NP-hard problems, the calculation of even the stability ball of radius 1 for an optimal solution is computationally intensive (i.e., a suitable polynomial algorithm is absent when \(P \neq NP\)). In using greedy algorithms for solving the set covering problem (knapsack problem) with the stability radius \(r = O(1)\), there are polynomial algorithms for calculating the stability ball of radius \(r\) for an \(\ln m\)-approximate solution (1-approximate solution).
Keywords:
complexity of sensitivity analysis; stability radius of a problem; stability ball of radius \(r\) for an \(\epsilon\)-approximate problem solutionReferences:
| [1] | D. Fernandez-Baca and B. Venkatachalam, “Sensitivity analysis in combinatorial optimization,” in: T. Gonzalez (ed.), Handbook of Approximation Algorithms and Metaheuristics, Chapman&Hall/CRC Computer and Information Science Series, Boca Raton (2007), pp. 30.-1-30.-29. · Zbl 1306.90132 |
| [2] | V. K. Leontiev and K. Kh. Mamutov, “Stability of solutions in problems of Boolean linear programming,” Computational Mathematics and Mathematical Physics, 28, No. 10, 1475-1481 (1988) · Zbl 0695.90062 |
| [3] | Yu. N. Sotskov, “Stability analysis of an approximate solution of a Boolean problem of minimization of a linear form,” Computational Mathematics and Mathematical Physics, 33, No. 5, 785-795 (1993) · Zbl 0799.90110 |
| [4] | N. Chakravarti and A. P. M. Wagelmans, “Calculation of stability radii for combinatorial optimization problems,” Operations Research Letters, 23, 1-7 (1998). · Zbl 0954.90037 · doi:10.1016/S0167-6377(98)00031-5 |
| [5] | I. V. Sergienko, Mathematical Models and Methods for Solving Discrete Optimization Problems [in Russian], Naukova Dumka, Kyiv (1985). · Zbl 0667.90058 |
| [6] | I. V. Sergienko and N. V. Filonenko, “Solution of some stability problems in integer linear programming,” Dop. AN URSR, Ser. A, No. 6, 79-82 (1982). · Zbl 0502.90063 |
| [7] | S. Van Hoesel and A. Wagelmans, “On the complexity of postoptimality analysis of 0/1 programs,” Discrete Applied Mathematics, 91, 251-263 (1999). · Zbl 0917.90250 · doi:10.1016/S0166-218X(98)00151-6 |
| [8] | C. Blair, “Sensitivity analysis for knapsack problems: A negative result,” Discrete Applied Mathematics, 81, 133-139 (1998). · Zbl 0895.90155 · doi:10.1016/S0166-218X(97)00080-2 |
| [9] | G. J. Woeginger, “Sensitivity analysis for knapsack problems: Another negative result,” Discrete Applied Mathematics, 92, 247-251 (1999). · Zbl 0957.90124 · doi:10.1016/S0166-218X(99)00053-0 |
| [10] | V. A. Mikhailyuk, “General approach to estimating the complexity of postoptimality analysis for discrete optimization problems,” Cybernetics and Systems Analysis, 46, No. 2, 290-295 (2010) · Zbl 1208.90118 · doi:10.1007/s10559-010-9206-1 |
| [11] | V. A. Mikhailyuk and N. V. Lishchuk, “Sensitivity analysis of the knapsack problem: A negative result,” Cybernetics and Systems Analysis, 49, No. 2, 201-204 (2013) · Zbl 1306.90133 · doi:10.1007/s10559-013-9500-9 |
| [12] | V. A. Mikhailyuk, “Reoptimization of max <Emphasis Type=”Italic“>k-cover: Approximation ratio threshold,” Cybernetics and Systems Analysis, 48, No. 2, 242-248 (2012) · Zbl 1306.90132 · doi:10.1007/s10559-012-9403-1 |
| [13] | V. A. Chvatal, “A greedy heuristic for the set covering problem,” Mathematics of Operation Research, 4, No. 3, 233-235 (1979) · Zbl 0443.90066 · doi:10.1287/moor.4.3.233 |
| [14] | N. N. Kuzyurin and S. A. Fomin, Efficient Algorithms and Complexity of Computations [in Russian], Moscow Institute of Physics and Technology, Moscow (2008). · Zbl 0443.90066 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
