|
Article information
2017 , Volume 22, ¹ 2, p.115-126
Prolubnikov A.V.
On an approach to set covering problem with interval weights and its computational complexity
Purpose. To obtain an approximation of the optimal solution of the set covering problem with interval weights and to estimate weights of the possible solutions. To estimate computational complexity of numerical realization of the presented approach. Methodology. discrete optimization, interval analysis, probability theory. Findings. An approach to obtain the estimations of weights for the possible solutions of the set covering problem with interval uncertainties is presented. We show that complexity of the numerical realization of the approach is non-decreasing step function of the interval widths. It is shown that the considered problem may be computationally hard even for small values of the parameters. An approach to the modification of such problems by means of their correction is presented. It facilitates the reduction of the problem to make it close to the initial one in accordance with certain criterion and keeps it nevertheless numerically solvable. Originality/value. An approach for obtaining an approximate solution of the covering problem with interval uncertainties in the weights is presented. Estimates of the weights for possible solutions of the problem is obtained. The computational complexity of the numerical implementation of the approach is estimated. It is shown that the covering problem with interval weights can be computationally complex for small values of its parameters.
[full text]
Keywords: the set covering problem, interval uncertainty, computational complexity
Author(s):
Prolubnikov Alexander Vyacheslavovich
Associate Professor
Office: Omsk F.M. Dostoevsky State University
Address: 644077, Russia, Omsk, Mira avenue 55-a
Phone Office: (3812) 64-42-38
E-mail: a.v.prolubnikov@mail.ru
SPIN-code: 4729-9643 References:
[1] Garey, M., Johnson, D. Computers and intractability: a guide to the theory of NPcompletness. New York: W.H. Freeman & Co; 1978: 352.
[2] Farahani, R.Z., Asgari, N., Heidari, N., Hosseininia, M., Goh, M. Covering problems in facility location: A review. Computers & Industrial Engineering. 2012; 62(1):368–407.
[3] Kearns, M.J. The computational complexity of machine learning. The MIT Press; 1990: 176.
[4] Milena, M. Set cover with requirements and costs evolving over time. Randomization, Approximation, and Combinatorial Optimization. Algorithms and Techniques. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer; 1999; (1671):63–72.
[5] Gao, B.J., Ester, M., Cai, J.-Y., Schulte, O., Xiong, H. The minimum consistent subset cover problem and its applications in data mining. Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, KDD ’07, New York, NY, USA; 2007: 310–319.
[6] Prolubnikov, A.V. The set cover problem with interval weights and the greedy algorithm for its solution. Computational Technologies. 2015; 20(6):70-84. (In Russ.)
[7] Chvatal, V. A greedy heuristic for the set-covering problem. Mathematics of operation research. 1979; 4(3):233–235.
[8] Feige, U. A threshhold of ln n for approximating set cover. Journal of the ACM (JACM). 1998; 45(4):634–652.
[9] Shary, S.P. Interval analysis or Monte-Carlo methods? Computational Technologies. 2007; 12(1):103–115. (In Russ.)
[10] OR-Library. Available at: http://people.brunel.ac.uk/˜mastjjb/jeb/info.html (accessed: 25.04.2016).
Bibliography link:
Prolubnikov A.V. On an approach to set covering problem with interval weights and its computational complexity // Computational technologies. 2017. V. 22. ¹ 2. P. 115-126
|
