A tight analysis of the greedy algorithm for set cover

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A tight analysis of the greedy algorithm for set cover

Full text

Pdf (540 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-eighth annual ACM symposium on Theory of computing table of contents

Philadelphia, Pennsylvania, United States

Pages: 435 - 441

Year of Publication: 1996

ISBN:0-89791-785-5

Author

Petr Slavík

Department of Mathematics, State University of New York at Buffalo, Buffalo, NY

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 14, Downloads (12 Months): 110, Citation Count: 30

Additional Information:

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/237814.237991 What is a DOI?

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	V. Chvltal. A Greedy Heuristic for the Set-covering Problem. Mathematics of Operations Research 4(1979), pp. 233-235.
	2	P. Crescenzi and V. Kann. A Compendium of NP Optimization Problems. Technical Report SI/RR-95/02, Department of Computer Science, University of Rome "La Sapienza', 1995.
	3	Uriel Feige, A threshold of ln n for approximating set cover (preliminary version), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.314-318, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237977]
	4	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	5	Magnús M. Halldórsson, Approximating discrete collections via local improvements, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.160-169, January 22-24, 1995, San Francisco, California, United States
	6	M.M. Halld6rsson. Approximating Set Cover via Local Improvements. JAIST Technical Report IS-RR-95- 0002F, 1995.
	7	D.S. Johnson. Approximation Algorithms for Combinatorial Problems. Journal of Computer and System Sciences 9(1974), pp. 256-278.
	8	R.M. Karp. Reducibility among Combinatorial Problems. In R.E. Miller and J.W. Thatcher, editors, Complexity of Computer Computations, 85-103, Plenum Press, New York, NY (1972).
	9	L. Lovazz. On the Ratio of Optimal Integral and Fractional Covers. Discrete Mathematics 13(1975), pp. 383- 390.
	10	Carsten Lund , Mihalis Yannakakis, On the hardness of approximating minimization problems, Journal of the ACM (JACM), v.41 n.5, p.960-981, Sept. 1994 [doi>10.1145/185675.306789]
	11	P. Slav~. Improved Performance of the Greedy Algorithm for Minimum Set Cover and Minimum Partial Cover. Technical Report 95-45, Department of Computer Science, SUNYat Buffalo,1995
	12	Aravind Srinivasan, Improved approximations of packing and covering problems, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.268-276, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225138]

CITED BY 30

	Uriel Feige, A threshold of ln n for approximating set cover (preliminary version), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.314-318, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Timothy M. Chan, Polynomial-time approximation schemes for packing and piercing fat objects, Journal of Algorithms, v.46 n.2, p.178-189, February 2003
	Aravind Srinivasan, New approaches to covering and packing problems, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.567-576, January 07-09, 2001, Washington, D.C., United States
	Uriel Feige, A threshold of ln n for approximating set cover, Journal of the ACM (JACM), v.45 n.4, p.634-652, July 1998
	Liang Huaguo , Sybille Hellebrand , Hans-Joachim Wunderlich, A mixed-mode BIST scheme based on folding compression, Journal of Computer Science and Technology, v.17 n.2, p.203-212, March 2002
	Piotr Berman , Bhaskar DasGupta , Ming-Yang Kao, Tight approximability results for test set problems in bioinformatics, Journal of Computer and System Sciences, v.71 n.2, p.145-162, August 2005
	Laurent Alfandari , Vangelis Th. Paschos, Master-Slave Strategy and Polynomial Approximation, Computational Optimization and Applications, v.16 n.3, p.231-245, Sept. 2000
	Fabian Kuhn , Roger Wattenhofer, Constant-time distributed dominating set approximation, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.25-32, July 13-16, 2003, Boston, Massachusetts
	Claude Chaudet , Eric Fleury , Isabelle Guérin Lassous , Hervé Rivano , Marie-Emilie Voge, Optimal positioning of active and passive monitoring devices, Proceedings of the 2005 ACM conference on Emerging network experiment and technology, October 24-27, 2005, Toulouse, France
	Orestis A. Telelis , Vassilis Zissimopoulos, Absolute o(logm) error in approximating random set covering: an average case analysis, Information Processing Letters, v.94 n.4, p.171-177, 31 May 2005
	Fabian Kuhn , Roger Wattenhofer, Constant-time distributed dominating set approximation, Distributed Computing, v.17 n.4, p.303-310, May 2005
	Frank Nielsen, On point covers of c-oriented polygons, Theoretical Computer Science, v.263 n.1-2, p.17-29, July 28 2001
	Giorgio Ausiello , Aristotelis Giannakos , Vangelis Th. Paschos, Greedy algorithms for on-line set-covering and related problems, Proceedings of the 12th Computing: The Australasian Theroy Symposium, p.145-151, January 16-19, 2006, Hobart, Australia
	Noga Alon , Dana Moshkovitz , Shmuel Safra, Algorithmic construction of sets for k-restrictions, ACM Transactions on Algorithms (TALG), v.2 n.2, p.153-177, April 2006
	Bruno Escoffier , Vangelis Th. Paschos, Completeness in approximation classes beyond APX, Theoretical Computer Science, v.359 n.1, p.369-377, 14 August 2006
	Stefano Bistarelli , Simon N. Foley , Barry O'Sullivan, A soft constraint-based approach to the cascade vulnerability problem, Journal of Computer Security, v.13 n.5, p.699-720, October 2005
	Cristina Bazgan , Jérôme Monnot , Vangelis Th. Paschos , Fabrice Serrière, On the differential approximation of MIN SET COVER, Theoretical Computer Science, v.332 n.1-3, p.497-513, 28 February 2005
	Michael Roy Fox , David C. Brogan , Paul F. Reynolds, Jr., Approximating component selection, Proceedings of the 36th conference on Winter simulation, December 05-08, 2004, Washington, D.C.
	Harish D , Pooja N. Darera , Jayant R. Haritsa, On the production of anorexic plan diagrams, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
	Piotr Berman , Bhaskar DasGupta, Approximating the online set multicover problems via randomized winnowing, Theoretical Computer Science, v.393 n.1-3, p.54-71, March, 2008
	Dongwook Lee , Gayathri Chandrasekaran , Mukundan Sridharan , Prasun Sinha, Association management for data dissemination over wireless mesh networks, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.51 n.15, p.4338-4355, October, 2007
	Nurcan Tezcan , Wenye Wang, TTS: a two-tiered scheduling mechanism for energy conservation in wireless sensor networks, International Journal of Sensor Networks, v.1 n.3/4, p.213-228, January 2006
	Harish D. , Pooja N. Darera , Jayant R. Haritsa, Identifying robust plans through plan diagram reduction, Proceedings of the VLDB Endowment, v.1 n.1, August 2008
	Shady Copty , Shai Fine , Shmuel Ur , Elad Yom-Tov , Avi Ziv, A probabilistic alternative to regression suites, Theoretical Computer Science, v.404 n.3, p.219-234, September, 2008
	Arnaud Legrand , Alan Su , Frédéric Vivien, Minimizing the stretch when scheduling flows of divisible requests, Journal of Scheduling, v.11 n.5, p.381-404, October 2008
	Benjamin N. Jackson , Patrick S. Schnable , Srinivas Aluru, Consensus Genetic Maps as Median Orders from Inconsistent Sources, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.5 n.2, p.161-171, April 2008
	Beata Zielosko , Marcin Piliszczuk, Greedy Algorithm for Attribute Reduction, Fundamenta Informaticae, v.85 n.1-4, p.549-561, September 2008
	Dimo Brockhoff , Eckart Zitzler, Objective reduction in evolutionary multiobjective optimization: Theory and applications, Evolutionary Computation, v.17 n.2, p.135-166, Summer 2009
	N. Bourgeois , B. Escoffier , V. Th. Paschos, Efficient approximation of min set cover by moderately exponential algorithms, Theoretical Computer Science, v.410 n.21-23, p.2184-2195, May, 2009
	Mikhail Ju. Moshkov , Marcin Piliszczuk , Beata Zielosko, Greedy Algorithm for Construction of Partial Association Rules, Fundamenta Informaticae, v.92 n.3, p.259-277, August 2009