On the red-blue set cover problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the red-blue set cover problem

Full text

Pdf (888 KB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms table of contents

San Francisco, California, United States

Pages: 345 - 353

Year of Publication: 2000

ISBN:0-89871-453-2

Authors

Robert D. Carr	Sandia National Labs, Albuquerque, NM and Multiprogram Laboratory, Lockheed Martin Company
Srinivas Doddi	Los Alamos National Laboratory, P.O. Box 1663, MS B265, Los Alamos, NM
Goran Konjevod	Dept. of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA
Madhav Marathe	Los Alamos National Laboratory, P.O. Box 1663, MS B265, Los Alamos, NM

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIAM : Society for Industrial and Applied Mathematics

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 91, Citation Count: 4

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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

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	Advanced methods for medicare fraud waste and abuse detection project. Los Alamos National Laboratory, Internal Report, June 1998. Prepared for the Health care and Finance Agency as Phase III report.
	2	NYS-LANL medicaid FWA detection project scoping paper detection project. Los Alamos National Laboratory, Internal Report, Dec 1997.
	3	M. Alekhnovich, S. Buss, S. Moran, and T. Pitassi. Minimum propositional proof length is np-hard to linearly approximate, manuscript, 1998.
	4	Sanjeev Arora , Carsten Lund, Hardness of approximations, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
	5	Nicolò Cesa-Bianchi , Yoav Freund , David P. Helmbold , David Haussler , Robert E. Schapire , Manfred K. Warmuth, How to use expert advice, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.382-391, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167198]
	6	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
	7	I. Dinur and S. Safra. On the hardness of approximating label cover. ECCC Report 15, 1999.
	8	G. Dobson. Worst-case analysis of greedy heuristics for integer programming with nonnegative data. Math. Oper. Res., 7:515-531, 1982.
	9	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 [doi>10.1145/301250.301447]
	10	M. Elkin and D. Peleg. The hardness of approximating spanner problems. Unpublished manuscript, 1999.
	11	U. Feige. Private communication.
	12	Yoav Freund , Robert E. Schapire , Yoram Singer , Manfred K. Warmuth, Using and combining predictors that specialize, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.334-343, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258616]
	13	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
	14	Michael Goldwasser , Rajeev Motwani, Intractability of Assembly Sequencing: Unit Disks in the Plane, Proceedings of the 5th International Workshop on Algorithms and Data Structures, p.307-320, August 06-08, 1997
	15	M. GrStschel, L. Lov~sz, and A. Schrijver. Geometric Algorithms and Combinatorial Optimization. Springer, 1988.
	16	R. Jacob, G. Konjevod, S. Krumke, M. Marathe, R. Ravi, and H. Wirth. The minimum label path problem. Unpublished manuscript, Los Alamos National Laboratory, 1999.
	17	D. S. Johnson. Approximation algorithms for combinatorial problems. J. Comput. System Sci., 9:256-278, 1974.
	18	Sven O. Krumke , Hans-Christoph Wirth, On the minimum label spanning tree problem, Information Processing Letters, v.66 n.2, p.81-85, April 1998 [doi>10.1016/S0020-0190(98)00034-9 ]
	19	A. Panconesi and A. Srinivasan. On a routing problem. Unpublished manuscript, 1999.
	20	Sridhar Rajagopalan , Vijay V. Vazirani, Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs, SIAM Journal on Computing, v.28 n.2, p.525-540, April 1999 [doi>10.1137/S0097539793260763]
	21	D. Rosenkrantz. Private communication.

CITED BY 4

	Michael Elkin , David Peleg, (1 + &egr;&Bgr;)-spanner constructions for general graphs, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.173-182, July 2001, Hersonissos, Greece
	David Peleg, Approximation algorithms for the Label-CoverMAX and Red-Blue Set Cover problems, Journal of Discrete Algorithms, v.5 n.1, p.55-64, March, 2007
	Alberto Caprara , Giuseppe F. Italiano , G. Mohan , Alessandro Panconesi , Aravind Srinivasan, Wavelength rerouting in optical networks, or the Venetian Routing problem, Journal of Algorithms, v.45 n.2, p.93-125, November 2002
	Jérôme Monnot, The labeled perfect matching in bipartite graphs, Information Processing Letters, v.96 n.3, p.81-88, 15 November 2005