Englert, Matthias, Voecking, Berthold and Winkler, Melanie (2009) Economical caching with stochastic prices. In: 5th International Symposium on Stochastic Algorithms - Foundations and Applications, Hokkaido Univ, Sapporo, JAPAN, OCT 26-28, 2009. Published in: Lecture Notes in Computer Science, Vol.5792 pp. 179-190.

Full text not available from this repository.

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:	Conference Item (Paper)
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:	Lecture Notes in Computer Science
Publisher:	Springer
ISBN:	978-3-642-04943-9
ISSN:	0302-9743
Editor:	Watanabe, O and Zeugmann, T
Date:	2009
Volume:	Vol.5792
Number of Pages:	12
Page Range:	pp. 179-190
Identification Number:	10.1007/978-3-642-04944-6
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
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 26-28, 2009
URI:	http://wrap.warwick.ac.uk/id/eprint/6526

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item