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

Cicalese F, Laber ES (2005)
In: ALGORITHMS - ESA 2005. 3669. SPRINGER-VERLAG BERLIN: 664-676.

Conference Paper | Published | English

No fulltext has been uploaded

Author
;
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.
Publishing Year
ISSN
PUB-ID

Cite this

Cicalese F, Laber ES. An optimal algorithm for querying priced information: Monotone Boolean functions and game trees. In: ALGORITHMS - ESA 2005. Vol 3669. SPRINGER-VERLAG BERLIN; 2005: 664-676.
Cicalese, F., & Laber, E. S. (2005). An optimal algorithm for querying priced information: Monotone Boolean functions and game trees. ALGORITHMS - ESA 2005, 3669, 664-676.
Cicalese, F., and Laber, E. S. (2005). “An optimal algorithm for querying priced information: Monotone Boolean functions and game trees” in ALGORITHMS - ESA 2005, vol. 3669, (SPRINGER-VERLAG BERLIN), 664-676.
Cicalese, F., & Laber, E.S., 2005. An optimal algorithm for querying priced information: Monotone Boolean functions and game trees. In ALGORITHMS - ESA 2005. no.3669 SPRINGER-VERLAG BERLIN, 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, vol. 3669, SPRINGER-VERLAG BERLIN, 2005, pp.664-676.
Cicalese, F., Laber, E.S.: An optimal algorithm for querying priced information: Monotone Boolean functions and game trees. ALGORITHMS - ESA 2005. 3669, p. 664-676. SPRINGER-VERLAG BERLIN (2005).
Cicalese, F, and Laber, ES. “An optimal algorithm for querying priced information: Monotone Boolean functions and game trees”. ALGORITHMS - ESA 2005. SPRINGER-VERLAG BERLIN, 2005.Vol. 3669. 664-676.
This data publication is cited in the following publications:
This publication cites the following data publications:

Export

0 Marked Publications

Open Data PUB

Web of Science

View record in Web of Science®

Search this title in

Google Scholar