Abstract
A new approach, the extension matrix approach, is introduced and used to show that some optimization problems in general covering problem areNP-hard. Approximate solutions for these problems are given. Combining these approximate solutions, this paper presents an approximately optimal covering algorithm,AE1. Implementation shows thatAE1 is efficient and gives optimal or near optimal results.
Similar content being viewed by others
References
D. S. Johnson, Approximation Algorithm for Combinatorial Problems,J. of Comput. and Systems Sci. 9 (3):38–49 (May 1973).
Yu. I. Zhuravlev, O Nevozmozhnosti Postroeniya Minimalnykh Normalnykh Form Funksii Algebry Logiki v Odnom Klasse Algoritmov,Doklady AN SSSR,132 (3):504–506 (1960).
I. L. Vasilev, Trudnosti Minimizatsii Bulevykh Funksii na Osnove Universalnykh Podkhodov,Doklady AN SSSR, Vol. 171, No. 1 (1966).
R. S. Michalski, On the Quasi-Minimal Solution of the General Covering Problem,Proc. of the Fifth Int. Symp. on Infor. Proc. (FCIP 69), Vol. A3 (Switching Circuits), Yugoslavia, Bled (October 1969).
R. S. Michalski, A Variable-Valued Logic and Its Application to Pattern Recognition and Machine Learning,Multiple-Valued Logic and Computer Science, Rine, D. (Ed.), North-Holland, pp. 506–534, (1975).
R. S. Michalski, A Theory and Methodology of Inductive Learning,Machine Learning, Michalski, R. S., Carbonell, J. G., and Mitchell, T. M. (Eds.), Tioga Publishing Company, Palo Alto, California, pp. 83–135 (1983).
J. R. Hong, User's Guide and Implementation for Automatic Rule Acquisition Program AE1, to appear in Reports of the Intelligent Systems Group, Department of Computer Science, University of Illinois (1986).
J. R. Hong, On the Disjoint Extension Matrices Approach in the General Covering Problem, to appear in Reports of the Intelligent Systems Group, Department of Computer Science, University of Illinois (1986).
Author information
Authors and Affiliations
Additional information
This research was supported in part by the National Science Foundation under Grant DCR 84-06801, Office of Naval Research under Grant N00014-82-K-0186, Defense Advanced Research Project Agency under Grant N00014-K-85-0878, and Education Ministry of the People's Republic of China.
On leave from Harbin Institute of Technology, Harbin, China.
Rights and permissions
About this article
Cite this article
Hong, J. AE1: An extension matrix approximate method for the general covering problem. International Journal of Computer and Information Sciences 14, 421–437 (1985). https://doi.org/10.1007/BF00991183
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF00991183