License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.05031.8
URN: urn:nbn:de:0030-drops-606
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2005/60/
Go to the corresponding Portal

Fujiwara, Hiroshi ; Iwama, Kazuo

Average-Case Competitive Analyses for Ski-Rental Problems

pdf-format:
05031.FujiwaraHiroshi.ExtAbstract.60.pdf (0.07 MB)

Abstract

Let $s$ be the ratio of the cost for purchasing skis over the cost for renting them. Then the famous result for the ski-rental problem shows that skiers should buy their skis after renting them $(s-1)$ 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 average-case 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:DagSemProc.05031.8,
  author =	{Fujiwara, Hiroshi and Iwama, Kazuo},
  title =	{{Average-Case Competitive Analyses for Ski-Rental Problems}},
  booktitle =	{Algorithms for Optimization with Incomplete Information},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5031},
  editor =	{Susanne Albers and Rolf H. M\"{o}hring and Georg Ch. Pflug and R\"{u}diger Schultz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2005/60},
  URN =		{urn:nbn:de:0030-drops-606},
  doi =		{10.4230/DagSemProc.05031.8},
  annote =	{Keywords: online algorithm , competitive analysis}
}

Keywords: online algorithm , competitive analysis
Collection: 05031 - Algorithms for Optimization with Incomplete Information
Issue Date: 2005
Date of publication: 30.05.2005

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI