The Library
Economical caching with stochastic prices
Tools
Englert, Matthias, Voecking, Berthold and Winkler, Melanie (2009) Economical caching with stochastic prices. In: Watanabe, O and Zeugmann, T, (eds.) Stochastic Algorithms : Foundations and Applications. Lecture Notes in Computer Science, Volume 5792 . Springer, pp. 179190. ISBN 9783642049439
PDF
fulltext19.pdf  Published Version Restricted to Repository staff only  Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader Download (201Kb) 
Official URL: http://dx.doi.org/10.1007/9783642049446_15
Abstract
In the economical caching problem, an online algorithm is given a sequence of prices for a certain commodity. The algorithm has to manage a buffer of fixed capacity over time. We assume that time proceeds in discrete steps. In step i, the commodity is available at price c(i) is an element of [alpha, beta], where beta > alpha >= 0 and c(i) is an element of N. One unit of the commodity is consumed per step. The algorithm can buy this unit at the current price c(i), can take a previously bought unit from the storage, or can buy more than one unit at price c(i) and put the remaining units into the storage. In this paper, we study the economical caching problem in a probabilistic analysis, that is, we assume that the prices are generated by a random walk with reflecting boundaries alpha and beta. We are able to identify the optimal online algorithm in this probabilistic model and analyze its expected cost and its expected savings, i.e., the cost that it saves in comparison to the cost that would arise without having a buffer. In particular, we compare the savings of the optimal online algorithm with the savings of the optimal offline algorithm in a probabilistic competitive analysis and obtain tight bounds (up to constant factors) on the ratio between the expected savings of these two algorithms.
Item Type:  Book Item  

Subjects:  Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software  
Divisions:  Faculty of Science > Computer Science  
Series Name:  Lecture Notes in Computer Science  
Journal or Publication Title:  Stochastic Algorithms : Foundations and Applications  
Publisher:  Springer  
ISBN:  9783642049439  
ISSN:  03029743  
Book Title:  Stochastic Algorithms : Foundations and Applications  
Editor:  Watanabe, O and Zeugmann, T  
Official Date:  2009  
Dates: 


Volume:  Volume 5792  
Number of Pages:  12  
Page Range:  pp. 179190  
Identification Number:  10.1007/9783642049446_15  
Status:  Peer Reviewed  
Publication Status:  Published  
Access rights to Published version:  Restricted or Subscription Access  
Funder:  DFG, Engineering and Physical Sciences Research Council (EPSRC)  
Grant number:  GK/1298 “AlgoSyn” (DFG); EP/F043333/1 (EPSRC)  
Conference Paper Type:  Paper  
Title of Event:  5th International Symposium on Stochastic Algorithms  Foundations and Applications  
Type of Event:  Conference  
Location of Event:  Hokkaido Univ, Sapporo, JAPAN  
Date(s) of Event:  OCT 2628, 2009  
URI:  http://wrap.warwick.ac.uk/id/eprint/6526 
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Actions (login required)
View Item 