Efficient sequences of trials

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficient sequences of trials

Full text

Pdf (873 KB)

Source

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

Baltimore, Maryland

SESSION: Session 11B table of contents

Pages: 737 - 746

Year of Publication: 2003

ISBN:0-89871-538-5

Authors

Edith Cohen	AT&T research labs, Florham park, NJ
Amos Fiat	Tel Aviv University, Tel Aviv, Israel
Haim Kaplan	Tel Aviv University, Tel Aviv, Israel

Sponsors

: SIAM Activity Group on Discrete Mathematics
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

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

Additional Information:

abstract 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

ABSTRACT

We introduce a problem called sequential trial optimization, a generalization of the well studied set cover problem with a new objective function. We give a simple algorithm that achieves a constant factor approximation to this problem. Sequential trial optimization naturally arises in heterogenous search environments such as peer to peer networks.

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. Chvátal. A greedy heuristic for the set-covering problem. Math. of Oper. Res., 4:233--235, 1979.
	2	E. Cohen, A. Fiat, and H. Kaplan. Associative search in peer to peer networks: Harnessing latent semantics. Manuscript, 2002.
	3	E. Cohen, A. Fiat, and H. Kaplan. A case for associative peer to peer overlays. In Proceedings of HotNets-I, ACM SIGCOMM, 2002.
	4	Edith Cohen , Scott Shenker, Replication strategies in unstructured peer-to-peer networks, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
	5	Open Source Community. Gnutella. In http://gnutella.wego.com/, 2001.
	6	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 [doi>10.1145/285055.285059]
	7	KaZaA file sharing network. KaZaA. In http://www.kazaa.com/, 2002.
	8	Morpheus file sharing system. Morpheus. In http://www.musiccity.com/, 2002.
	9	L. Lovász. On the ratio of optimal integral and fractional covers. Discrete Mathematics, 13:383--390, 1975.
	10	Qin Lv , Pei Cao , Edith Cohen , Kai Li , Scott Shenker, Search and replication in unstructured peer-to-peer networks, Proceedings of the 16th international conference on Supercomputing, June 22-26, 2002, New York, New York, USA [doi>10.1145/514191.514206]
	11	FastTrack Peer-to-Peer technology company. FastTrack. In http://www.fasttrack.nu/, 2001.

CITED BY 6

	Anne Condon , Amol Deshpande , Lisa Hellerstein , Ning Wu, Flow algorithms for two pipelined filter ordering problems, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA
	Edith Cohen , Carsten Lund, Packet classification in large ISPs: design and evaluation of decision tree classifiers, ACM SIGMETRICS Performance Evaluation Review, v.33 n.1, June 2005
	Archan Misra , Abhishek Roy , Sajal K. Das, Information-theory based optimal location management schemes for integrated multi-system wireless networks, IEEE/ACM Transactions on Networking (TON), v.16 n.3, p.525-538, June 2008
	Shivnath Babu , Rajeev Motwani , Kamesh Munagala , Itaru Nishizawa , Jennifer Widom, Adaptive ordering of pipelined stream filters, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France
	Edith Cohen , Amos Fiat , Haim Kaplan, Associative search in peer to peer networks: Harnessing latent semantics, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.51 n.8, p.1861-1881, June, 2007
	Edith Cohen , Amos Fiat , Haim Kaplan, Associative search in peer to peer networks: Harnessing latent semantics, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.51 n.8, p.1861-1881, June, 2007