An approach to estimating the complexity of probabilistic procedures for the postoptimality analysis of discrete optimiz
- PDF / 101,672 Bytes
- 7 Pages / 595.276 x 793.701 pts Page_size
- 86 Downloads / 229 Views
CYBERNETICS AN APPROACH TO ESTIMATING THE COMPLEXITY OF PROBABILISTIC PROCEDURES FOR THE POSTOPTIMALITY ANALYSIS OF DISCRETE OPTIMIZATION PROBLEMS UDC 519.854
V. A. Mikhailyuk
Abstract. It is shown that ZPP- and RP-probabilistic polynomial postoptimality analysis procedures for finding an optimal solution of a set cover problem that differs from the original problem in one position of the constraints matrix do not exist if an optimal solution of the original problem is known and if ZPP ¹ NP ( RP ¹ NP ) . A similar result holds for the knapsack problem. Keywords: postoptimality analysis, ZPP-probabilistic polynomial postoptimality analysis procedure, RP-probabilistic polynomial postoptimality analysis procedure.
At the present time, the involvement of elements of randomness in developing algorithms is a standard approach. Efficiency and simplicity underlie random algorithms, which frequently makes randomization a peculiar springboard for solving complicated problems in various applications. Randomness becomes an integral part of the development of applied software systems especially in the field of communications, cryptography, data processing, and discrete optimization. There are a lot of cases when deterministic computations require enormous time, whereas random methods can be successfully applied. However, a saving of time in random algorithms increases the risk of computation of an incorrect answer, and this risk can be reduced to a minimum. In solving a concrete optimization problem with a fixed collection of input data, a great deal of information is usually processed, and only some elements of this information can be used for solving the problem. The other information is lost. This circumstance poses the problem of the expedient involvement of redundant information to solve other optimization problems “close” to the initial one in some sense or other. The postoptimality analysis of discrete optimization problems [1–4] provides for the answer to the following questions. — How does an optimal solution to a concrete problem change if its coefficient values change in a definite manner? — How can the information obtained in solving some problem by a concrete method be used to solve the changed problem? — What minimum additional information should be accumulated in solving an initial problem with a view to efficiently solving the changed problem? Of interest are elements of randomness that are introduced in performing the postoptimality analysis of discrete optimization problems and also the consideration of probabilistic postoptimal procedures. (Here, results from [5, 6] are used.)
V. M. Glushkov Institute of Cybernetics, National Academy of Science of Ukraine, Kyiv, Ukraine, [email protected]. Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 3–10, November–December 2012. Original article submitted December 16, 2010. 1060-0396/12/4806-0807
©
2012 Springer Science+Business Media New York
807
1. SOME CONCEPTS OF THE THEORY OF PROBABILISTIC COMPUTATIONS Hereafter, we will not say about th
Data Loading...
