Ski Rental Problem

Introduction

You want to go on holiday for skiing but your old skis are too small. The question is (i) to rent or (ii) to buy new skis. When you rent them, then you pay R for each day. But, maybe you like it so much that you go more often skiing in the next years. Then it would be better to buy ski for B (with B > R). But, maybe you do not like skiing anymore after the first day of skiing. What should you do?

Variables

  • y – unknown total days where skis are required (offline information)
  • x – rental duration (decision variable)
  • B – buy price of skis
  • R – rent price of skis

Mathematical Program

    \begin{equation*} 				\setlength\arraycolsep{1.5pt} 				\begin{array}{l l l r c r@{\quad\quad} r} 								\text{given:}		&  & \multicolumn{3}{l}{y, R,B}    & 		& \\ 				\min\limits_{x}         &  & xR  &  +   &  B \textbf{1}  &   & \text{cost function}       \\ 				\text{s.t. } 	 & \mathrm{(I)} 	& x & \leq   & y & & \text{skiing-ability constraint} \\ 								 & \mathrm{(II)}    & \textbf{1} & = & 0 &  :x=y & \text{only rent constraint} \\ 								 & \mathrm{(III)}    & \textbf{1} & = & 1 &  :x<y & \text{rent+buy constraint} \\ 							 	 & \mathrm{(IV)}    & x & \geq & 0 &   & \text{future constraint} \\ 				\end{array} 		\end{equation*}

Offline Solution

    \begin{equation*}\begin{array}{l c l}OPT(y) & = & \begin{cases}Ry & \text{if }Ry < B \\B & \text{if } Ry \geq B\end{cases}\\ & = &  \min\{Ry,B\} \end{array}\end{equation*}


Algorithms

Pure Algorithm 1: Just-Buy Algorithm

    \begin{equation*}  \begin{array}{l c l}  c & = & \max\limits_{y>0} \frac{ALG(y)}{OPT(y)} \\ & = & \max\limits_{y>0} \frac{B}{\min\{Ry,B\}} \\  & \leq & \frac{B}{R}  \end{array}  \end{equation*}

Buy at the first day and never rent. This algorithm is competitive.

Pure Algorithm 2: Never-Buy Algorithm

    \begin{equation*} 		\begin{array}{l c l} 		c & = & \max\limits_{y>0} \frac{ALG(y)}{OPT(y)} \\ 		& = & \max\limits_{y>0} \frac{yR}{\min\{Ry,B\}} \\ 		& = & \frac{\infty}{B} \\ 		& = & \infty 		\end{array} 		\end{equation*}

Always rent and never buy. This algorithm is not competitive.

Mixed Algorithm: RentX Algorithm

    \begin{equation*} 		\begin{array}{l c l} 		c & = & \max\limits_{y>0, x<y} \frac{ALG(y)}{OPT(y)} \\ 		& \leq & \max\limits_{y>0, x<y} \frac{xR+B}{\min\{Ry,B\}} \\ 		\end{array} 		\end{equation*}

Rent x days and then buy. This algorithm is competitive. Note: In all possible scenarios you will buy, i.e., the rental duration is lower than the skiing duration x<y. At least, c is always bounded, but only determinable with concrete parameter x.

Optimal Algorithm: RentX^* Algorithm

    \begin{equation*} 		\begin{array}{l c l} 		\text{too early error} 	& = & \text{too late error} \\ 		\frac{xR+B}{Ry}					& = & 	\frac{xR+B}{B}		\\ 		\frac{xR+B}{R(x+1)}					& = & 	\frac{xR+B}{B}		\\				\frac{xR+B}{Rx+R}					& = & 	\frac{xR+B}{B}		\\ 		xR+R					& = & 	B		\\ 		\end{array} 	\end{equation*}

Rent x^*=\frac{B}{R}-1 days and then buy. This algorithm is competitive and optimal. x^*=\frac{B}{R}-1 \Rightarrow c^*=\frac{x^*R+B}{B}=\frac{B-R+B}{B}=\frac{2B-R}{B}=2-\frac{R}{B}

Conclusion

The optimal solution is to rent ski for \frac{B}{R}-1 days for R each day and then buy the ski for B. In the worst-case you will have at maximum 2-\frac{R}{B} times more costs than the offline solution.

Leave a Reply

Your email address will not be published. Required fields are marked *