Fujiwara, Hiroshi ;
Iwama, Kazuo
AverageCase Competitive Analyses for SkiRental Problems
Abstract
Let $s$ be the ratio of the cost for purchasing skis over the cost for renting them. Then the famous result for the skirental problem shows that skiers should buy their skis after renting them $(s1)$ times, which gives us an optimal competitive ratio of $2\frac{1}{s}$. In practice, however, it appears that many skiers buy their skis before this optimal point of time and also many skiers keep renting them forever. In this paper we show that these behaviors of skiers are quite reasonable by using an {\em averagecase competitive ratio}. For an exponential input distribution $f(t) = \lambda e^{\lambda t}$, optimal strategies are (i) if $\frac{1}{\lambda} \leq s$, then skiers should rent their skis forever and (ii) otherwise should purchase them after renting approximately $s^2\lambda \;\;(
BibTeX  Entry
@InProceedings{fujiwara_et_al:DSP:2005:60,
author = {Hiroshi Fujiwara and Kazuo Iwama},
title = {AverageCase Competitive Analyses for SkiRental Problems},
booktitle = {Algorithms for Optimization with Incomplete Information},
year = {2005},
editor = {Susanne Albers and Rolf H. M{\"o}hring and Georg Ch. Pflug and R{\"u}diger Schultz},
number = {05031},
series = {Dagstuhl Seminar Proceedings},
ISSN = {18624405},
publisher = {Internationales Begegnungs und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2005/60},
annote = {Keywords: online algorithm , competitive analysis}
}
Keywords: 

online algorithm , competitive analysis 
Seminar: 

05031  Algorithms for Optimization with Incomplete Information

Issue date: 

2005 
Date of publication: 

30.05.2005 