%0 Journal Article
%T The Multi-shop Ski Rental Problem
%A Lingqing Ai
%A Xian Wu
%A Lingxiao Huang
%A Longbo Huang
%A Pingzhong Tang
%A Jian Li
%J Computer Science
%D 2014
%I arXiv
%X We consider the {\em multi-shop ski rental} problem. This problem generalizes the classic ski rental problem to a multi-shop setting, in which each shop has different prices for renting and purchasing a pair of skis, and a \emph{consumer} has to make decisions on when and where to buy. We are interested in the {\em optimal online (competitive-ratio minimizing) mixed strategy} from the consumer's perspective. For our problem in its basic form, we obtain exciting closed-form solutions and a linear time algorithm for computing them. We further demonstrate the generality of our approach by investigating three extensions of our basic problem, namely ones that consider costs incurred by entering a shop or switching to another shop. Our solutions to these problems suggest that the consumer must assign positive probability in \emph{exactly one} shop at any buying time. Our results apply to many real-world applications, ranging from cost management in \texttt{IaaS} cloud to scheduling in distributed computing.
%U http://arxiv.org/abs/1404.2671v1