A threshold of ln n for approximating set cover (preliminary version)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A threshold of ln n for approximating set cover (preliminary version)

Full text

Pdf (553 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: 314 - 318

Year of Publication: 1996

ISBN:0-89791-785-5

Author

Uriel Feige

Department of Applied Math and Computer Science, The Weizmann Institute, Rehovot 76100, Israel

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 32, Citation Count: 58

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.237977 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	S Arora, (~,. Lund, R. Motw~ni, M. Sudan, M. Szegedy. "Proof verification and hardness of approximation prol~lems". 33rd FO(?S, ld-~3, 1992.
	2	M. Bellare , S. Goldwasser , C. Lund , A. Russeli, Efficient probabilistically checkable proofs and applications to approximations, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.294-304, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167174]
	3	Michael Ben-Or , Shafi Goldwasser , Joe Kilian , Avi Widgerson, Multi-prover interactive proofs: how to remove intractability assumptions, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.113-131, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62223]
	4	V. Chvatal. "A greedy heuristic for the set covering problem". Math. Oper. Res., d, 1979, ~33-235.
	5	M. l)ye~, A. Frieze. "A simple heuristic for the p-center problem". ()per. }~es. Lett., 3, 1985, 285-288.
	6	Uriel Feige , Joe Kilian, Impossibility results for recycling random bits in two-prover proof systems, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.457-468, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225183]
	7	Uriel Feige , László Lovász, Two-prover one-round proof systems: their power and their problems (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.733-744, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129783]
	8	.1. H astad, 5. Phillips, S. SMra. "A well characterized approximation problem". Proc. ~nd Israel Syrup. on Theory of (_/omputing and Systems, 261-265, 1993.
	9	D. Hochbaum, D. Shmoys. "A best possible approximation algorithm for the k-center problem". Math. Oper. {te.~.. 10. 1985, 180-18~.
	10	W. Hsll, (~. Nemhauser. "Easy and hard bottleneck locatiol, problems". Dzscrete Applied Math., 1, 1979, 20.9---21b
	11	D. Johnson. "Approxmlation Mgorithms for combinatorial prot-,lem.~*' J. ('/omput. ,5'y.stc'm ~5'cz. 9. 1974, 256- :278.
	12	L. Lovasz. "()It the ratio of the optimal integral and tra.ctmnM covers". D~screte Mathematics 1,? (1975) ?&.?-390
	13	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]
	14	M. Naor , L. J. Schulman , A. Srinivasan, Splitters and near-optimal derandomization, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.182, October 23-25, 1995
	15	C,. Papadimitrion, M. Yannakakis. "Optimization, approximation, and complexity classes". JCSS, J3, 1991, 425-440.
	16	Ran Raz, A parallel repetition theorem, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.447-456, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225181]
	17	Petr Slavík, A tight analysis of the greedy algorithm for set cover, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.435-441, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237991]
	18	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 58

	Rakesh Agrawal , Johannes Gehrke , Dimitrios Gunopulos , Prabhakar Raghavan, Automatic subspace clustering of high dimensional data for data mining applications, ACM SIGMOD Record, v.27 n.2, p.94-105, June 1998
	Sanjeev Arora , Carsten Lund , Rajeev Motwani , Madhu Sudan , Mario Szegedy, Proof verification and the hardness of approximation problems, Journal of the ACM (JACM), v.45 n.3, p.501-555, May 1998
	Oded Goldreich , Shafi Goldwasser, On the limits of non-approximability of lattice problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.1-9, May 24-26, 1998, Dallas, Texas, United States
	Sanjeev Arora, The approximability of NP-hard problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.337-348, May 24-26, 1998, Dallas, Texas, United States
	Amotz Bar-Noy , Sudipto Guha , Joseph (Seffi) Naor , Baruch Schieber, Multicasting in heterogeneous networks, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.448-453, May 24-26, 1998, Dallas, Texas, United States
	C. Douglass Bateman , C. S. Helvig , Gabriel Robins , Alexander Zelikovsky, Provably good routing tree construction with multi-port terminals, Proceedings of the 1997 international symposium on Physical design, p.96-102, April 14-16, 1997, Napa Valley, California, United States
	Venky Harinarayan , Anand Rajaraman , Jeffrey D. Ullman, Implementing data cubes efficiently, ACM SIGMOD Record, v.25 n.2, p.205-216, June 1996
	Howard Karloff , Milena Mihail, On the complexity of the view-selection problem, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.167-173, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
	Moses Charikar , Chandra Chekuri , Ashish Goel , Sudipto Guha, Rounding via trees: deterministic approximation algorithms for group Steiner trees and k-median, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.114-123, May 24-26, 1998, Dallas, Texas, United States
	Moses Charikar , Chandra Chekuri , To-yat Cheung , Zuo Dai , Ashish Goel , Sudipto Guha , Ming Li, Approximation algorithms for directed Steiner problems, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.192-200, January 25-27, 1998, San Francisco, California, United States
	Tetsuo Asano , Naoki Katoh , Hisao Tamaki , Takeshi Tokuyama, Covering points in the plane by k-tours: towards a polynomial time approximation scheme for general k, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.275-283, May 04-06, 1997, El Paso, Texas, United States
	Rong-chii Duh , Martin Fürer, Approximation of k-set cover by semi-local optimization, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.256-264, May 04-06, 1997, El Paso, Texas, United States
	Sudipto Guha , Samir Khuller, Greedy strikes back: improved facility location algorithms, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.649-657, January 25-27, 1998, San Francisco, California, United States
	Lujun Jia , Rajmohan Rajaraman , Torsten Suel, An efficient distributed algorithm for constructing small dominating sets, Distributed Computing, v.15 n.4, p.193-205, December 2002
	Yevgeniy Dodis , Sanjeev Khanna, Design networks with bounded pairwise distance, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.750-759, May 01-04, 1999, Atlanta, Georgia, United States
	Naveen Garg , Goran Konjevod , R. Ravi, A polylogarithmic approximation algorithm for the Steiner group tree problem, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.253-259, January 25-27, 1998, San Francisco, California, United States
	Guy Kortsarz , David Peleg, Approximating shallow-light trees, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.103-110, January 05-07, 1997, New Orleans, Louisiana, United States
	Shai Ben-David , Nadav Eiron , Philip M. Long, On the difficulty of approximately maximizing agreements, Journal of Computer and System Sciences, v.66 n.3, p.496-514, May 2003
	Liming Cai , David Juedes , Iyad Kanj, The inapproximability of non-NP-hard optimization problems, Theoretical Computer Science, v.289 n.1, p.553-571, 23 October 2002
	Elliot Anshelevich , Anirban Dasgupta , Eva Tardos , Tom Wexler, Near-optimal network design with selfish agents, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Madhav V. Marathe , R. Ravi , Ravi Sundaram, Service-constrained network design problems, Nordic Journal of Computing, v.3 n.4, p.367-387, Winter 1996
	Stavros G. Kolliopoulos, Approximating covering integer programs with multiplicity constraints, Discrete Applied Mathematics, v.129 n.2-3, p.461-473, 01 August 2003
	Andrei Z. Broder , Moses Charikar , Michael Mitzenmacher, A derandomization using min-wise independent permutations, Journal of Discrete Algorithms, v.1 n.1, p.11-20, February 2003
	Toshihiro Fujito , Takashi Doi, A 2-approximation NC algorithm for connected vertex cover and tree cover, Information Processing Letters, v.90 n.2, p.59-63, 30 April 2004
	Jiangzhuo Chen , Robert D. Kleinberg , László Lovász , Rajmohan Rajaraman , Ravi Sundaram , Adrian Vetta, (Almost) tight bounds and existence theorems for confluent flows, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Petr Slavík, A tight analysis of the greedy algorithm for set cover, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.435-441, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	C. S. Helvig , G. Robins , A. Zelikovsky, Improved approximation bounds for the group Steiner problem, Proceedings of the conference on Design, automation and test in Europe, p.406-413, February 23-26, 1998, Le Palais des Congrés de Paris, France
	Jie Gao , Leonidas Guibas , John Hershberger , Li Zhang , An Zhu, Discrete mobile centers, Proceedings of the seventeenth annual symposium on Computational geometry, p.188-196, June 2001, Medford, Massachusetts, United States
	Stephan Eidenbenz, Approximation algorithms for terrain guarding, Information Processing Letters, v.82 n.2, p.99-105, 30 April 2002
	F. k. Hwang , Wenan Zang, Detecting Corrupted Pages in M Replicated Large Files, IEEE Transactions on Parallel and Distributed Systems, v.8 n.12, p.1241-1245, December 1997
	David Peleg, Local majorities, coalitions and monopolies in graphs: a review, Theoretical Computer Science, v.282 n.2, p.231-257, 10 June 2002
	Reuven Bar-Yehuda , Keren Bendel , Ari Freund , Dror Rawitz, Local ratio: A unified framework for approximation algorithms. In Memoriam: Shimon Even 1935-2004, ACM Computing Surveys (CSUR), v.36 n.4, p.422-463, December 2004
	Himanshu Gupta , Inderpal Singh Mumick, Selection of Views to Materialize in a Data Warehouse, IEEE Transactions on Knowledge and Data Engineering, v.17 n.1, p.24-43, January 2005
	Christian Glaßer , Steffen Reith , Heribert Vollmer, The complexity of base station positioning in cellular networks, Discrete Applied Mathematics, v.148 n.1, p.1-12, 30 April 2005
	Mikhail Alekhnovich , Sanjeev Arora , Iannis Tourlakis, Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	F. Grandoni , J. Könemann , A. Panconesi , M. Sozio, Primal-dual based distributed algorithms for vertex cover with semi-hard capacities, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA
	Rajmohan Rajaraman, Topology control and routing in ad hoc networks: a survey, ACM SIGACT News, v.33 n.2, June 2002
	Frank Nielsen, On point covers of c-oriented polygons, Theoretical Computer Science, v.263 n.1-2, p.17-29, July 28 2001
	Patrice Calégaria, , Frédéric Guidec , Pierre Kuonen , Frank Nielsen, Combinatorial optimization algorithms for radio network planning, Theoretical Computer Science, v.263 n.1-2, p.235-265, July 28 2001
	David S. Johnson, The NP-completeness column: The many limits on approximation, ACM Transactions on Algorithms (TALG), v.2 n.3, p.473-489, July 2006
	Yigal Bejerano , Rajeev Rastogi, Robust monitoring of link delays and faults in IP networks, IEEE/ACM Transactions on Networking (TON), v.14 n.5, p.1092-1103, October 2006
	Jon Feldman , S Muthukrishnan , Martin Pal , Cliff Stein, Budget optimization in search-based advertising auctions, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA
	Richard Nock , Frank Nielsen, Self-improved gaps almost everywhere for the agnostic approximation of monomials, Theoretical Computer Science, v.377 n.1-3, p.139-150, May, 2007
	Yehuda Ben-Shimol , Boaz Ben-Moshe , Yoav Ben-Yehezkel , Amit Dvir , Michael Segal, Automated antenna positioning algorithms for wireless fixed-access networks, Journal of Heuristics, v.13 n.3, p.243-263, June 2007
	Rakesh Agrawal , Johannes Gehrke , Dimitrios Gunopulos , Prabhakar Raghavan, Automatic Subspace Clustering of High Dimensional Data, Data Mining and Knowledge Discovery, v.11 n.1, p.5-33, July 2005
	Endre Boros , Takashi Horiyama , Toshihide Ibaraki , Kazuhisa Makino , Mutsunori Yagiura, Finding Essential Attributes from Binary Data, Annals of Mathematics and Artificial Intelligence, v.39 n.3, p.223-257, November 2003
	Ding-Zhu Du , Ronald L. Graham , Panos M. Pardalos , Peng-Jun Wan , Weili Wu , Wenbo Zhao, Analysis of greedy approximations with nonsubmodular potential functions, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.167-175, January 20-22, 2008, San Francisco, California
	Decheng Dai , Changyuan Yu, A 5+epsilon (Porson)-approximation algorithm for minimum weighted dominating set in unit disk graph, Theoretical Computer Science, v.410 n.8-10, p.756-765, March, 2009
	Zhao Zhang , Xiaofeng Gao , Weili Wu, Algorithms for connected set cover problem and fault-tolerant connected set cover problem, Theoretical Computer Science, v.410 n.8-10, p.812-817, March, 2009
	Xueliang Li , Xiaoyan Zhang, On the minimum monochromatic or multicolored subgraph partition problems, Theoretical Computer Science, v.385 n.1-3, p.1-10, October, 2007
	Deying Li , Qin Liu , Xiaodong Hu , Xiaohua Jia, Energy efficient multicast routing in ad hoc wireless networks, Computer Communications, v.30 n.18, p.3746-3756, December, 2007
	Jean-Charles Creput , Abderrafiaa Koukam, Local search study of honeycomb clustering problem for cellular planning, International Journal of Mobile Network Design and Innovation, v.1 n.2, p.153-160, September 2006
	Beata Zielosko , Marcin Piliszczuk, Greedy Algorithm for Attribute Reduction, Fundamenta Informaticae, v.85 n.1-4, p.549-561, September 2008
	Erez Kantor , David Peleg, Approximate hierarchical facility location and applications to the bounded depth Steiner tree and range assignment problems, Journal of Discrete Algorithms, v.7 n.3, p.341-362, September, 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
	Christer Bäckström, Computational aspects of reordering plans, Journal of Artificial Intelligence Research, v.9 n.1, p.99-137, August 1998
	Richard Nock, Inducing interpretable voting classifiers without trading accuracy for simplicity: theoretical results, approximation algorithms, and experiments, Journal of Artificial Intelligence Research, v.17 n.1, p.137-170, July 2002
	Mikhail Ju. Moshkov , Marcin Piliszczu , Beata Zielosko, Greedy Algorithms withWeights for Construction of Partial Association Rules, Fundamenta Informaticae, v.94 n.1, p.101-120, January 2009