Query strategies for priced information (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Query strategies for priced information (extended abstract)

Full text

Pdf (1.14 MB)

Source

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

Portland, Oregon, United States

Pages: 582 - 591

Year of Publication: 2000

ISBN:1-58113-184-4

Authors

Moses Charikar	Computer Science Department, Stanford University, CA
Ronald Fagin	IBM Almaden Reseach Center, 650 Harry Road, San Jose, CA
Venkatesan Guruswami	Laboratory for Computer Science, MIT, Cambridge, MA
Jon Kleinberg	Department of Computer Science, Cornell University, Ithaca, NY
Prabhakar Raghavan	IBM Almaden Reseach Center, 650 Harry Road, San Jose, CA
Amit Sahai	Laboratory for Computer Science, MIT, Cambridge, MA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 20, Citation Count: 4

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/335305.335382 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	Avrim Blum , Prasad Chalasani , Don Coppersmith , Bill Pulleyblank , Prabhakar Raghavan , Madhu Sudan, The minimum latency problem, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.163-171, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195125]
	2	Allan Borodin , Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, NY, 1998
	3	B. Bollobas, Extremal Graph Theory, Academic Press, 1978.
	4	Clickshare Service Corp., www.clickshare.com.
	5	O. Madani, Efficient information gathering on the Internet, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.234, October 14-16, 1996
	6	Hector Garcia-Molina , Steven P. Ketchpel , Narayanan Shivakumar, Safeguarding and Charging for Information on the Internet, Proceedings of the Fourteenth International Conference on Data Engineering, p.182-189, February 23-27, 1998
	7	R. Heiman, A. Wigderson, "Randomized vs. Deterministic Decision Tree Complexity for Read-Once Boolean Functions," Complexity Theory, to appear.
	8	János Komlós , Yuan Ma , Endre Szemerédi, Matching nuts and bolts in O(n log n) time, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.232-241, January 28-30, 1996, Atlanta, Georgia, United States
	9	Elias Koutsoupias , Christos H. Papadimitriou , Mihalis Yannakakis, Searching a Fixed Graph, Proceedings of the 23rd International Colloquium on Automata, Languages and Programming, p.280-289, July 08-12, 1996
	10	D. Kreps, A Course in Micro-Economic Theory, Princeton University Press, 1990.
	11	Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
	12	Pricing Economic Access to Knowledge (PEAK) Home Page, http://www, lib. umich.edu/libhome/peak/papers.html.
	13	S. Sairamesh, C. Nikolaou, D. F. Ferguson and Y. Yemini. Economic Framework for Pricing and Charging in Digital Libraries. D-Lib Magazine, February 1996.
	14	M. Saks, A. Wigderson, "Probabilistic Boolean decision trees and the complexity of evaluating game trees;' Proc. IEEE FOCS, 1986.
	15	M. Snir, "Lower bounds on probabilistic linear decision trees," Theoretical Computer Science 38(1985), pp. 69-82.
	16	D. Tygar, "NetBill: An Internet Commerce System Optimized for Network-Delivered Systems" IEEE Personal Communications 2(1995), pp. 20-25.
	17	"What's the Value of Digital Information?", panel at ICEE Conf. on Electronic Commerce: Foundations for the Future, 1999.
	18	Yanjun Zhang, On the Optimality of Randomized $\alpha$-$\beta$ Search, SIAM Journal on Computing, v.24 n.1, p.138-147, Feb. 1995 [doi>10.1137/S009753979223037X]

CITED BY 4

	Sampath Kannan , Sanjeev Khanna, Selection with monotone comparison costs, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Haim Kaplan , Eyal Kushilevitz , Yishay Mansour, Learning with attribute costs, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Ashish Goel , Sudipto Guha , Kamesh Munagala, Asking the right questions: model-driven optimization using probes, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA
	Sudipto Guha , Kamesh Munagala, Model-driven optimization using adaptive probes, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.308-317, January 07-09, 2007, New Orleans, Louisiana