General approach to estimating the complexity of postoptimality analysis for discrete optimization problems. (English)
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.
Start
Contact
Print
General Help
