Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2017, 11:2, 193-203
Volume 24, No 2, 2017, P. 87-106
UDC 519.157.1
I. P. Chukhrov
Proof of covering minimality by generalizing the notion of independence
Abstract:
A method is proposed for obtaining lower bounds for the length of the shortest cover and complexity of the minimal cover based on the notion of independent family of sets. For the problem of minimization of Boolean functions, we provide the functions and construct coverings by faces of the set of unit vertices for which the suggested lower bounds can be achieved in the case of five or more variables. The lower bounds, based on independent sets, are unreachable and cannot be used as sufficient conditions for minimality of such functions.
Bibliogr. 11.
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
1. Institute of Computer Aided Design RAS,
19/18 Vtoraya Brestskaya St., 123056 Moscow, Russia
e-mail: chip@icad.org.ru
Received 27 April 2016
Revised 17 November 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. Al-Shihabi, 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, Two-level 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 greedy-like heuristic for the weighted set covering problem?, Oper. Res. Lett., 44, No. 3, 366–369, 2016.
