Mikhailyuk V. Estimates of complexity of postoptimality analysis and approximation algorithms for the reoptimization of discrete programming problems

It is shown that the conduct of postoptimality analysis (in worst-case) of NP-hard problems in itself is NP-hard. To obtain upper bounds on the approximation ratio of approximation reoptimization algorithms semidefinite (SDP-) and linear (LP-) relaxations of the original problems are used. We obtain sufficient conditions for the existence of polynomial optimal or threshold (the upper bound of approximation ratio coincident with the lower) approximation reoptimization algorithms of constraint satisfaction problems Ins-Max-EkCSP-P (CSPs): approximation resistance of the predicate P; truth of the unique game conjecture (UGC), as well as an accurate estimate of integrality gap of SDP-or LP - relaxation of the problem. Based on the analysis of reoptimization algorithms for set covering problem (replacing the 0 to 1 or 1 to 0 in the matrix of constraints) confirmed the possibility of high-quality "jumps" from one class to another class of approximation with the best quality of approximation. It "jumps" from class Log-APX to class APX. It is shown that for reoptimization of set covering problem when adding or release of any item in the set, there is no polynomial time approximation schemes (PTAS). The proposed approach for designing of polynomial optimal (threshold) approximation reoptimization algorithms for discrete programming problems triggered in the case of sublinear algorithms, in particular, the constant-time complexity. Based on the results of theoretical studies offered practical algorithm of postoptimality analysis to determine by branch and bound method the exact solutions of a family of related knapsack problems. Computer experiment shows its effectiveness.