TY  - JOUR
AB  - We study the function evaluation problem in the priced information framework introduced in [Charikar et al. 2002]. We characterize the best possible extremal competitive ratio for the class of game tree functions. Moreover, we extend the above result to the case when the cost of reading a variable depends on the value of the variable. In this new value dependent cost variant of the problem, we also exactly evaluate the extremal competitive ratio for the whole class of monotone Boolean functions.
DA  - 2008
KW  - Value dependent costs
KW  - Game trees
KW  - Function evaluation with priced information
LA  - eng
PY  - 2008
SN  - 0946-7831
TI  - Computing with Priced Information: game trees and the value dependent cost model
UR  - https://nbn-resolving.org/urn:nbn:de:hbz:361-14383
Y2  - 2024-11-22T07:40:41
ER  -