An Efficient Algorithm for Finding an Irredundant Set Cover

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An Efficient Algorithm for Finding an Irredundant Set Cover

Full text

Pdf (347 KB)

Source

Journal of the ACM (JACM) archive
Volume 21 , Issue 3 (July 1974) table of contents

Pages: 351 - 355

Year of Publication: 1974

ISSN:0004-5411

Authors

Charles R. Kime	Department of Electrical and Computer Engineering, University of Wisconsin, Madison, Wisconsin
Ramachendra P. Batni	Bell Telephone Laboratories, Naperville, IL and University of Wisconsin, Madison, Wisconsin
Jeffrey D. Russell	Collins Radio Company, Cedar Rapids, IA and University of Wisconsin, Madison, Wisconsin

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 37, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/321832.321833 What is a DOI?

ABSTRACT

The set covering problem is considered and an efficient procedure for finding an irredundant cover is presented. For an m × n cover table, the execution time of the procedure is, in the worst case, proportional to mn. Methods are suggested for obtaining alternate irredundant covers based on an initially obtained irredundant cover. The basic cost-independent algorithm is heuristically extended to consider costs so that a reduced-cost irredundant cover can be obtained. A summary of some computational experience is presented, which indicates that the procedure is fast and applicable to large problems.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	BALINSKI, M.L. Integer programmning: methods, uses, computation. Manage. Sci. 12, 3 (Nov. 1965), 253-313.
	2	BOWMAN, R. M., AnD McVEY, E.S. A method for the fast approximate solution of large prime implicant charts. IEEE Trans. Computers C-I, 3 (March 1972), 317-318.
	3	BUSENIK, V. Weighting method for the determination of the irredundant set of prime implicants. 1EEE Trans. Computers C-21, 12 (Dec. 1972), 1449-1451.
	4	DAS, S.R. An approach for simplifying switching functions by utilizing the cover table representation. IEEE Trans. Computers C-20, 3 (March 1971), 355--359.
	5	Du, MIN-WEN. A way to find a lower bound for the minimal solution of the covering problem. IEEE Trans. Computers C-M, 3 (March 1972), 317-318.
	6	LiN, S. Heuristic techniques for solving large combinatorial problems on a computer. In Lecture Notes in Operations Research and Mathematical Systems 8, R. Banerji and M. D. Mesarovic, Eds., Springer-Verlag, New York, 410-418.
	7	ROTH, R. Computer solutions to minimum-cover problems. Op. Res. 17, 3 (May-June 1969), 455-465.
	8	Ronald D. Koncal , Harvey M. Salkin, Set Covering by an All Integer Algorithm: Computational Experience, Journal of the ACM (JACM), v.20 n.2, p.189-193, April 1973 [doi>10.1145/321752.321753]