Abstract
We study competitive function evaluation in the context of computing with priced information. A function f has to be evaluated for a fixed but unknown choice of the values of the variables. Each variable x of f has an associated cost c(x), which has to be paid to read the value of x. The problem is to design algorithms that compute the function querying the values of the variables sequentially while trying to minimize the total cost incurred. The evaluation of the performance of the algorithms is made by employing competitive analysis. We determine the best possible extremal competitive ratio for the classes of threshold trees, game trees, and monotone boolean functions with constrained minterms, by providing a polynomial-time algorithm whose competitiveness matches the known lower bounds.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Carmo, R., Feder, T., Kohayakawa, Y., Laber, E., Motwani, R., O’Callaghan, L., Panigrahy, R., Thomas, D.: Querying priced information in databases: the conjunctive case (2004) (submitted)
Charikar, M., Fagin, R., Guruswami, V., Kleinberg, J., Raghavan, P., Sahai, A.: Query strategies for priced information. JCSS: Journal of Computer and System Sciences 64, 785–819 (2002)
Cicalese, F., Laber, E.S.: A new strategy for querying priced information. In: Proceedings of the 37th ACM Symposium on Theory of Computing. ACM Press, Baltimore (2005) (to appear)
Gupta, A., Kumar, A.: Sorting and selection with structured costs. In: IEEE (ed.), 42nd IEEE Symposium on Foundations of Computer Science, pp. 416–425 (2001)
Gupta, A., Stahl, D.O., Whinston, A.B.: Pricing of services on the internet. In: IMPACT: How IC2 Research Affects Public Policy and Business Markets. Quorum Books (forthcoming)
Guruswami, V., Laber, E.: Personal communications (2003)
Kannan, S., Khanna, S.: Selection with monotone comparison costs. In: Proceedings of the fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2003), pp. 10–17 (2003)
Karchmer, M., Linial, N., Newman, I., Saks, M., Wigderson, A.: Combinatorial characterization of read-once formulae. Discrete Mathematics, 114 (1993)
Khanna, S., Tan, W.: On computing functions with uncertainty. In: Symposium on Principles of Database Systems, pp. 171–182 (2001)
Laber, E.: A randomized competitive algorithm for evaluating priced AND/OR trees. In: Diekert, V., Habib, M. (eds.) STACS 2004. LNCS, vol. 2996, pp. 501–512. Springer, Heidelberg (2004)
Laber, E., Parekh, O., Ravi, R.: Randomized approximation algorithms for query optimization problems on two processors. In: Möhring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol. 2461, pp. 649–661. Springer, Heidelberg (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cicalese, F., Laber, E.S. (2005). An Optimal Algorithm for Querying Priced Information: Monotone Boolean Functions and Game Trees. In: Brodal, G.S., Leonardi, S. (eds) Algorithms – ESA 2005. ESA 2005. Lecture Notes in Computer Science, vol 3669. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11561071_59
Download citation
DOI: https://doi.org/10.1007/11561071_59
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-29118-3
Online ISBN: 978-3-540-31951-1
eBook Packages: Computer ScienceComputer Science (R0)