Reoptimization of set covering problems
- PDF / 89,300 Bytes
- 5 Pages / 595.276 x 793.701 pts Page_size
- 93 Downloads / 188 Views
REOPTIMIZATION OF SET COVERING PROBLEMS UDC 519.854
V. A. Mikhailyuk
Abstract. If an element is inserted into or removed from a set, then the set covering problem can be æ 1 ö reoptimized with some ratio çç 2 ÷÷ , where m is the number of elements of the set. A similar è ln m + 1 ø result holds if an arbitrary number 1< p < m of elements of the set is inserted or removed. Keywords: reoptimization, r-approximation algorithm.
At the present time, in solving NP-hard problems, a new computational paradigm has arisen, namely, reoptimization [1–7]. The most well-known approach to the solution of such problems lies in the development and use of approximation algorithms that yield a solution close to optimal in polynomial time. The quality of an approximate solution (usually measured as the ratio of values of approximate and optimal solutions) must be guaranteed. The line of investigation connected with the development of best approximation algorithms and classification of problems that is based on the approximation quality that is reached in polynomial time occupy an important place in theoretical investigations of informatics over the past two decades. The concept of reoptimization is as follows. Let Ï be some NP-hard (or, possibly, NP-complete) problem, and let I be its initial instance whose optimal solution is known. A new instance I¢ of the problem Ï is proposed that is obtained as a result of some “insignificant” changes in the instance I. How can knowledge on the optimal solution of I be efficiently used for the computation of some exact or approximate solution of the instance I ¢ ? The objective of reoptimization in applying approximate methods is the use of knowledge on the solution of the initial instance I (a) to achieve a better approximation quality (approximation ratio) of I ¢, (b) to create a more efficient (more fast) algorithm for determination of an optimal (or close to optimal) solution to I¢ , or (c) to provide the fulfillment of the first and second conditions. The following results on the reoptimization of discrete optimization problems are well known. After the insertion of an elementary disjunction, the reoptimization of Max Weighted Sat (the weighted maximum satisfiability problem) is approximable with the ratio 0.81 though Max Weighted Sat is approximable with the ratio 0.77 [7]. After the insertion of a vertex into a graph, the reoptimization of Min Vertex Cover (the minimum vertex cover problem) is approximable with the ratio 1.5, and Min Vertex Cover is approximable with the ratio 2 [7]. After the insertion of a (terminal or nonterminal) vertex, the reoptimization of Min Steiner Tree (the minimum Steiner tree problem) is approximable with the ratio 1.5 and Min Steiner Tree is approximable with the ratio 1+ ln( 3) / 2 » 1. 55 [4]. Worthy of mention is a series of works on the reoptimization of the Traveling Salesman Problem (TSP) [1–3, 5]. For example, the minimum metric distance TSP (Min TSP) is approximable with the ratio 1.5, its reoptimization after the insertion of a new node is approxi
Data Loading...
