ENRU
English version: Journal of Applied and Industrial Mathematics, 2017, 11:2, 193203 

Volume 24, No 2, 2017, P. 87106 UDC 519.157.1
Keywords: set covering problem, complexity, shortest cover, minimum cover, independent set, lower bound, condition of minimality. DOI: 10.17377/daio.2017.24.540 Igor P. Chukhrov ^{1} Received 27 April 2016 References[1] A. V. Eremeev, L. A. Zaozerskaya, and A. A. Kolokolov, The set covering problem: Complexity, algorithms, and experimental investigations, Diskretn. Anal. Issled. Oper., Ser. 2, 7, No. 2, 22–46, 2000 [Russian].[2] G. I. Zabinyako, Implementation of algorithms for solution to the set covering problem and analysis of their efficiency, Vychisl. Technol., 12, No. 6. 50–58, 2007 [Russian]. Translated in Comput. Technol., 12, No. 6. 50–58, 2007. [3] V. K. Leont’ev, Discrete optimization, Zh. Vychisl. Mat. Mat. Fiz., 47, No. 2, 338–352, 2007 [Russian]. Translated in Comput. Math. Math. Phys., 47, No. 2, 328–340, 2007. [4] I. P. Chukhrov, On complexity measures of complexes of faces in the unit cube, Diskretn. Anal. Issled. Oper., 20, No. 6, 77–94, 2013 [Russian]. Translated in J. Appl. Ind. Math., 8, No. 1, 9–19, 2014. [5] I. P. Chukhrov, On a minimization problem for a set of boolean functions, Diskretn. Anal. Issled. Oper., 22, No. 3, 75–97, 2015 [Russian]. Translated in J. Appl. Ind. Math., 9, No. 3, 335–350, 2015. [6] S. AlShihabi, M. Arafeh, and M. Barghash, An improved hybrid algorithm for the set covering problem. Comput. Ind. Eng., 85, 328–334, 2015. [7] O. Coudert, On solving covering problems, in Proc. 33rd Design Automation Conf., Las Vegas, NV, USA, June 3–7, 1996, pp. 197–202, ACM, New York, 1996. [8] O. Coudert and T. Sasao, Twolevel logic minimization, in S. Hassoun and T. Sasao, eds., Logic Synthesis and Verification, pp. 1–27, Kluwer Acad. Publ., Netherlands, 2002 (Springer Int. Ser. Eng. Comput. Sci., Vol. 654). [9] C. Gao, X. Yao, T. Weise, and J. Li, An efficient local search heuristic with row weighting for the unicost set covering problem, Eur. J. Oper. Res., 246, No. 3, 750–761, 2015. [10] N. Sapkota and C. H. Reilly, Simulating realistic set covering problems with known optimal solutions. Comput. Ind. Eng., 61, No. 1, 39–47, 2011. [11] F. J. Vasko, Y. Lu, and K. Zyma, What is the best greedylike heuristic for the weighted set covering problem?, Oper. Res. Lett., 44, No. 3, 366–369, 2016. 

© Sobolev Institute of Mathematics, 2015  