General approach to estimating the complexity of postoptimality analysis for discrete optimization problems. (English. Russian original) Zbl 1208.90118
Cybern. Syst. Anal. 46, No. 2, 290-295 (2010); translation from Kibern. Sist. Anal. 2010, No. 2, 134-141 (2010).
Summary: It is shown that there does not exist a polynomial algorithm to derive the optimal solution of a set cover problem that differs from the original problem in one position of the constraint matrix if the optimal solution of the original problem is known and \(P \neq NP\). A similar result holds for the knapsack problem.
MSC:
| 90C10 | Integer programming |
References:
| [1] | L. N. Kozeratskaya, T. T. Lebedeva, and I. V. Sergienko, ”Stability, parametric, and postoptimality analysis of discrete optimization problems,” Cybernetics, 19, No. 4, 522–534 (1983). · Zbl 0553.90069 · doi:10.1007/BF01068340 |
| [2] | I. V. Sergienko and V. P. Shilo, Discrete Optimization Problems: Challenges, Solution Techniques, Analysis [in Russian], Naukova Dumka, Kyiv (2003). |
| [3] | A. M. Geoffrion and R. Nauss, ”Parametric and postoptimality analysis in integer linear programming,” Management Science, 23, No. 5, 453–466 (1977). · Zbl 0358.90041 · doi:10.1287/mnsc.23.5.453 |
| [4] | G. M. Roodman, ”Postoptimality analysis in zero one programming by implicit enumeration,” Naval Res. Logist. Quart., 19, No. 3, 435–447 (1972). · Zbl 0262.90047 · doi:10.1002/nav.3800190304 |
| [5] | 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, Kluwer Academ. Publ., New York (1998), pp. 97–148. · Zbl 0914.90204 |
| [6] | Yu. N. Sotskov, V. K. Leontev, and E. N. Gordeev, ”Some concepts of stability analysis in combinatorial optimization,” Discrete Appl. Mathemat., 58, 169–190 (1995). · Zbl 0833.90098 · doi:10.1016/0166-218X(93)E0126-J |
| [7] | V. A. Emelichev and D. P. Podkopaev, ”Quantitative stability measure in a vector integer linear programming problem,” Zh. Vych. Mat. Mat. Fiz., 38, No. 11, 1801–1805 (1998). · Zbl 0964.90028 |
| [8] | V. K. Leont’ev, ”Stability in linear discrete problems,” Probl. Kibernetiki, Issue 35, 169–184 (1979). |
| [9] | S. Van Hoesel and A. Wagelmans, ”On the complexity of postoptimality analysis of 0/1 programs,” Discrete Appl. Mathemat., 91, 251–263 (1999). · Zbl 0917.90250 · doi:10.1016/S0166-218X(98)00151-6 |
| [10] | M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Co., New York (1979). · Zbl 0411.68039 |
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.
