Computing with Priced Information: game trees and the value dependent cost model

Cicalese F, Milanivc M (2008) Forschungsberichte der Technischen Fakultät, Abteilung Informationstechnik / Universität Bielefeld.
Bielefeld: Universität Bielefeld, Technische Fakultät.

Download
OA
Report | Published | English
Author
;
Abstract
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.
Publishing Year
ISSN
PUB-ID

Cite this

Cicalese F, Milanivc M. Computing with Priced Information: game trees and the value dependent cost model. Forschungsberichte der Technischen Fakultät, Abteilung Informationstechnik / Universität Bielefeld. Bielefeld: Universität Bielefeld, Technische Fakultät; 2008.
Cicalese, F., & Milanivc, M. (2008). Computing with Priced Information: game trees and the value dependent cost model (Forschungsberichte der Technischen Fakultät, Abteilung Informationstechnik / Universität Bielefeld). Bielefeld: Universität Bielefeld, Technische Fakultät.
Cicalese, F., and Milanivc, M. (2008). Computing with Priced Information: game trees and the value dependent cost model. Forschungsberichte der Technischen Fakultät, Abteilung Informationstechnik / Universität Bielefeld, Bielefeld: Universität Bielefeld, Technische Fakultät.
Cicalese, F., & Milanivc, M., 2008. Computing with Priced Information: game trees and the value dependent cost model, Forschungsberichte der Technischen Fakultät, Abteilung Informationstechnik / Universität Bielefeld, Bielefeld: Universität Bielefeld, Technische Fakultät.
F. Cicalese and M. Milanivc, Computing with Priced Information: game trees and the value dependent cost model, Forschungsberichte der Technischen Fakultät, Abteilung Informationstechnik / Universität Bielefeld, Bielefeld: Universität Bielefeld, Technische Fakultät, 2008.
Cicalese, F., Milanivc, M.: Computing with Priced Information: game trees and the value dependent cost model. Forschungsberichte der Technischen Fakultät, Abteilung Informationstechnik / Universität Bielefeld. Universität Bielefeld, Technische Fakultät, Bielefeld (2008).
Cicalese, Ferdinando, and Milanivc, Martin. Computing with Priced Information: game trees and the value dependent cost model. Bielefeld: Universität Bielefeld, Technische Fakultät, 2008. Forschungsberichte der Technischen Fakultät, Abteilung Informationstechnik / Universität Bielefeld.
Main File(s)
File Name
Access Level
OA Open Access

This data publication is cited in the following publications:
This publication cites the following data publications:

Export

0 Marked Publications

Open Data PUB

Search this title in

Google Scholar