Title | ||
---|---|---|
An optimal algorithm for querying priced information: monotone boolean functions and game trees |
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. |
Year | DOI | Venue |
---|---|---|
2005 | 10.1007/11561071_59 | ESA |
Keywords | Field | DocType |
associated cost,competitive function evaluation,total cost,game tree,optimal algorithm,monotone boolean function,competitive analysis,polynomial-time algorithm,lower bound,variables sequentially,possible extremal competitive ratio,competitive ratio | Boolean function,Monotonic function,Combinatorics,Mathematical optimization,Computer science,Upper and lower bounds,Algorithm,Bellman equation,Greedy algorithm,Deterministic algorithm,Game tree,Competitive analysis | Conference |
Volume | ISSN | ISBN |
3669 | 0302-9743 | 3-540-29118-0 |
Citations | PageRank | References |
5 | 0.48 | 9 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Ferdinando Cicalese | 1 | 450 | 48.20 |
Eduardo Sany Laber | 2 | 229 | 27.12 |