Skip to main content
Log in

AE1: An extension matrix approximate method for the general covering problem

  • Published:
International Journal of Computer & Information Sciences Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Similar content being viewed by others

References

  1. D. S. Johnson, Approximation Algorithm for Combinatorial Problems,J. of Comput. and Systems Sci. 9 (3):38–49 (May 1973).

    Google Scholar 

  2. Yu. I. Zhuravlev, O Nevozmozhnosti Postroeniya Minimalnykh Normalnykh Form Funksii Algebry Logiki v Odnom Klasse Algoritmov,Doklady AN SSSR,132 (3):504–506 (1960).

    Google Scholar 

  3. I. L. Vasilev, Trudnosti Minimizatsii Bulevykh Funksii na Osnove Universalnykh Podkhodov,Doklady AN SSSR, Vol. 171, No. 1 (1966).

  4. 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).

  5. 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).

  6. 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).

    Google Scholar 

  7. 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).

  8. 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).

Download references

Author information

Authors and Affiliations

Authors

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

Reprints 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

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF00991183

Key words

Navigation