An optimal algorithm for querying priced information: Monotone Boolean functions and game trees

Cicalese F, Laber ES (2005)
In: Algorithms – ESA 2005. 13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005. Proceedings. Stølting Brodal G, Leonardi S, European Association for Theoretical Computer Science (Eds); Lecture Notes in Computer Science, 3669. Berlin: Springer: 664-676.

Konferenzbeitrag | Veröffentlicht | Englisch
 
Download
Es wurden keine Dateien hochgeladen. Nur Publikationsnachweis!
Autor*in
Cicalese, Ferdinando; Laber, Eduardo Sany
Herausgeber*in
Stølting Brodal, Gerth; Leonardi, Stefano
herausgebende Körperschaft
European Association for Theoretical Computer Science
Abstract / Bemerkung
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.
Erscheinungsjahr
2005
Titel des Konferenzbandes
Algorithms – ESA 2005. 13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005. Proceedings
Serien- oder Zeitschriftentitel
Lecture Notes in Computer Science
Band
3669
Seite(n)
664-676
ISBN
9783540291183
ISSN
0302-9743
Page URI
https://pub.uni-bielefeld.de/record/1601085

Zitieren

Cicalese F, Laber ES. An optimal algorithm for querying priced information: Monotone Boolean functions and game trees. In: Stølting Brodal G, Leonardi S, European Association for Theoretical Computer Science, eds. Algorithms – ESA 2005. 13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005. Proceedings. Lecture Notes in Computer Science. Vol 3669. Berlin: Springer; 2005: 664-676.
Cicalese, F., & Laber, E. S. (2005). An optimal algorithm for querying priced information: Monotone Boolean functions and game trees. In G. Stølting Brodal, S. Leonardi, & European Association for Theoretical Computer Science (Eds.), Lecture Notes in Computer Science: Vol. 3669. Algorithms – ESA 2005. 13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005. Proceedings (pp. 664-676). Berlin: Springer. https://doi.org/10.1007/11561071_59
Cicalese, Ferdinando, and Laber, Eduardo Sany. 2005. “An optimal algorithm for querying priced information: Monotone Boolean functions and game trees”. In Algorithms – ESA 2005. 13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005. Proceedings, ed. Gerth Stølting Brodal, Stefano Leonardi, and European Association for Theoretical Computer Science, 3669:664-676. Lecture Notes in Computer Science. Berlin: Springer.
Cicalese, F., and Laber, E. S. (2005). “An optimal algorithm for querying priced information: Monotone Boolean functions and game trees” in Algorithms – ESA 2005. 13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005. Proceedings, Stølting Brodal, G., Leonardi, S., and European Association for Theoretical Computer Science eds. Lecture Notes in Computer Science, vol. 3669, (Berlin: Springer), 664-676.
Cicalese, F., & Laber, E.S., 2005. An optimal algorithm for querying priced information: Monotone Boolean functions and game trees. In G. Stølting Brodal, S. Leonardi, & European Association for Theoretical Computer Science, eds. Algorithms – ESA 2005. 13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005. Proceedings. Lecture Notes in Computer Science. no.3669 Berlin: Springer, pp. 664-676.
F. Cicalese and E.S. Laber, “An optimal algorithm for querying priced information: Monotone Boolean functions and game trees”, Algorithms – ESA 2005. 13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005. Proceedings, G. Stølting Brodal, S. Leonardi, and European Association for Theoretical Computer Science, eds., Lecture Notes in Computer Science, vol. 3669, Berlin: Springer, 2005, pp.664-676.
Cicalese, F., Laber, E.S.: An optimal algorithm for querying priced information: Monotone Boolean functions and game trees. In: Stølting Brodal, G., Leonardi, S., and European Association for Theoretical Computer Science (eds.) Algorithms – ESA 2005. 13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005. Proceedings. Lecture Notes in Computer Science. 3669, p. 664-676. Springer, Berlin (2005).
Cicalese, Ferdinando, and Laber, Eduardo Sany. “An optimal algorithm for querying priced information: Monotone Boolean functions and game trees”. Algorithms – ESA 2005. 13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005. Proceedings. Ed. Gerth Stølting Brodal, Stefano Leonardi, and European Association for Theoretical Computer Science. Berlin: Springer, 2005.Vol. 3669. Lecture Notes in Computer Science. 664-676.