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.

Report | Veröffentlicht| Englisch
 
Download
OA
Autor/in
Cicalese, Ferdinando; Milanivc, Martin
Abstract / Bemerkung
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.
Stichworte
Value dependent costs; Game trees; Function evaluation with priced information
Erscheinungsjahr
2008
ISSN
0946-7831
Page URI
https://pub.uni-bielefeld.de/record/2308930

Zitieren

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.
Alle Dateien verfügbar unter der/den folgenden Lizenz(en):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Volltext(e)
Access Level
OA Open Access
Zuletzt Hochgeladen
2019-09-06T08:57:52Z
MD5 Prüfsumme
428e8e813dccc166ea9db9418dd4eac4

Export

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Suchen in

Google Scholar