|
Article information
2015 , Volume 20, ¹ 6, p.72-86
Prolubnikov A.V.
The set cover problem with interval weights and the greedy algorithm for its solution
Purpose: We study the set cover problem when a set of weighted subsets of a set U is supposed to be given. Cover set of U is a collection of subsets of that set when the union of members of the set contains U. We need to choose a cover that contains sets which have minimum total weight. The specificity of our work is that we investigate the problem with interval weights of the subsets. Methodology: We introduce definitions of optimal and approximate solutions of the problem. Realization of the weights of given subsets is a possible variant of these weights. The weak optimal solution of the problem is a solution that is optimal for some realization. The strong optimal solution is a solution that is optimal for any realization. The united optimal solution is such a set of weak solutions that it contains an optimal solution for any possible realization. The united approximate solution is such a set of covers that contains approximate solutions for every realization. Findings: The theorem of characterization of the strong optimal solution is proved. The modification of the greedy algorithm for the problem is presented. The algorithm gives the united approximate solution as a result. For the uniform distributions of weights, we present a modification of the algorithm that could be used to find probabilities of the approximate solutions. Originality/value: The concepts of optimal and approximate solutions are presented for the set cover problem with interval weights. The theorem of characterization of the strong optimal solution is proved. The modification of the greedy algorithm for the set cover problem with interval weights is presented.
[full text]
Keywords: set cover problem, interval uncertainty, greedy algorithm
Author(s):
Prolubnikov Alexander Vyacheslavovich
Position: engineer
Office: Omsk Scientific Center of Siberian branch of the Russian Academy of Sciences
Address: 644010, Russia, Omsk, Marx avenue, 15
Phone Office: (3812) 64-42-38
E-mail: a.v.prolubnikov@mail.ru
SPIN-code: 4729-9643 References:
[1] Karp, R.M. Reducibility among combinatorial problems. Lectures of the pioneers of integer programming: 50 years of integer programming 1958-2008. Berlin; Heidelberg: Springer Verlag; 2010:219241. DOI: 10.1007/978-3-540-68279-0.
[2] Farahani, R.Z., Asgari, N., Heidari, N., Hosseininia, M., Goh, M. Covering problems in facility location: A review. Computers and Industrial Engineering. 2012; 62(1):368407.
[3] Kearns, M.J. The computational complexity of machine learning. Cambriege: MIT Press; 1990: 176.
[4] Milena, M. Set cover with requirements and costs evolving over time. Randomization,Approximation, and Combinatorial Optimization. Algorithms and Techniques: Vol. 1671 of Lecture Notes in Computer Science. Berlin, Heidelberg: Springer; 1999:6372.
[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, USA; 2007:310319.
[6] Zakrevskiy, A.D. Logicheskiy sintez kaskadnykh skhem [Logical synthesis of cascade schemes]. Moscow: Nauka; 1981: 416. (In Russ.)
[7] German, O.V., Efremov, O.V. An algorithm for the generalized set cover problem. Economics and Mathematical Methods. 1998; 34(4):134140. (In Russ.)
[8] Balas, E., Carrera, M.C. A dynamic subgradient-based branch and bound procedure for set covering. Operational Research. 1996; 44(6):875890.
[9] Balas, E., Ho, A. Set covering algorithms using cutting planes, heuristics, and subgradient optimization: a computational study. Mathematical Programming. 1980; (12):3760.
[10] Garfinkel, R.S., Nemhauser, G.L. Integer programming. New York: Wiley; 1972: 427.
[11] Eremeev, A.V., Kolokolov, A.A., Zaozerskaya, L.A. A hybrid algorithm for set covering problem. Proceedings of International Workshop on Discrete Optimization Methods in Sñheduling and Computer-Aided Design. Minsk; 2000:123129.
[12] Gomes, F.C., Meneses, C.N., Pardalos, P.M., Viana, G.V.R. Experimental analysis of approximation algorithms for the vertex cover and set covering problems. Computers and Operations Research. 2006; 33(12):35203534.
[13] Beasley, J.E. An algorithm for set covering problem. European Journal of Operational Research. 1987; (31):8593.
[14] Chvatal, V. A greedy heuristic for the set-covering problem. Mathematics of Operation Research. 1979; 4(3):233235.
[15] Feige, U. A threshhold of ln n for approximating set cover. Journal of the Association for Computing Machinery. 1998; 45(4):634652.
[16] Beraldi, P., Ruszczynski, A. The probabilistic set-covering problem. Operations Research. 2002; 50(6):956967.
[17] Hwang, M.J., Chiang, C.I., Liu, Y.H. Solving a fuzzy set-covering problem. Mathematical and Computer Modelling. 2004; 40(7):861865.
[18] Chiang, C.I., Hwang, M.J., Liu, Y.H. An alternative formulation for certain fuzzy set-covering problems. Mathematical and Computer Modelling. 2005; 42(34):363365.
[19] Fischetti, M., Monaci, M. Cutting plane versus compact formulations for uncertain (integer) linear programs. Mathematical Programming Computation. 2012; 4(3):239273.
[20] Pereira, P., Averbakh, I. The robust set covering problem with interval data. Annals of Operations Research. 2011; 207(1):119.
[21] Yaman, H., Karasan, O.E., Pinar, M.C. Longest path problem with interval data: Technical Report 9908, Department of Industrial Engineering, Bilkent University, 06533 Bilkent, Ankara, Turkey, 1999.
[22] Yaman, H., Karasan, O.E., Pinar, M.C. The robust minimum spanning tree problem with interval data. Operations Research Letters. 2001; 29(1):3140.
Bibliography link:
Prolubnikov A.V. The set cover problem with interval weights and the greedy algorithm for its solution // Computational technologies. 2015. V. 20. ¹ 6. P. 72-86
|
