DocumentCode
3098358
Title
Heuristic approach to binate covering problem
Author
Servít, Michal ; Zamazal, Jan
Author_Institution
Dept. of Comput., Czechoslovak Tech. Univ., Praha, Czechoslovakia
fYear
1992
fDate
16-19 Mar 1992
Firstpage
123
Lastpage
129
Abstract
Covering problem is a problem of extraction of a minimum cost subset from a given set that satisfies certain constraints expressed as a Boolean formula in conjunctive normal form. This problem is NP-hard, heuristic methods are thus of interest. The authors present two heuristic methods to finding a nearly minimal solution and compare them to each other. The authors derive the asymptotic complexity of the presented methods and report some computational results obtained for a number of randomly generated covering problems
Keywords
Boolean functions; computational complexity; minimisation of switching nets; set theory; Boolean formula; NP-hard; asymptotic complexity; binate covering problem; conjunctive normal form; heuristic methods; minimum cost subset; Automata; Business continuity; Costs; Design automation; History; Minimization methods; NP-hard problem; Operations research; Random number generation;
fLanguage
English
Publisher
ieee
Conference_Titel
Design Automation, 1992. Proceedings., [3rd] European Conference on
Conference_Location
Brussels
Print_ISBN
0-8186-2645-3
Type
conf
DOI
10.1109/EDAC.1992.205906
Filename
205906
Link To Document