# The Online Reservation Problem
## Appendix A Proof of Theorem 3  
Proof. : We begin by defining some notation. Let \(\beta>0\) an arbitrarily large real number, \(k\) and \(b\) arbitrary positive integers, \(\alpha\doteq\Delta^{\frac{1}{k}}\), and \(\epsilon>0\) arbitrarily small. Let \(q_{i}\doteq\left(1/\alpha^{i-1}\right)-\left(1/\alpha^{i}\right)\) for \(i\in[k]\) and \(q_{k+i}\doteq 1/\left(bx^{k}\right)\) for \(i\in[b]\). Let \(s_{1},s_{2},\ldots,s_{k+b}\) and \(s^{\prime}_{k+1},s^{\prime}_{k+2},\ldots,s^{\prime}_{k+b}\) be sequences of jobs, each with \(n\) jobs, as shown in Table 1. Each 2-tuple in Table 1 represents a job, with the first value in the tuple being the start time of the job and the second value being the job's duration. The jobs in the sequences are ordered by their arrival times. Appending these sequences one after another, we define sequences (instances) \(L_{1},L_{2},\ldots,L_{k+b}\) as described in Table 2. The arrival times of the jobs are such that the jobs in each of \(L_{1},L_{2},\ldots,L_{k+b}\) are ordered by their arrival times. A specific example of \(L_{1},L_{2},\ldots,L_{k+b}\) for the case when \(b=k=3\) and \(n=1\) is depicted in Figure 1. Define \(\mathcal{K}\doteq\{L_{1},L_{2},\ldots,L_{k+b}\}\). The probability distribution \(\mathcal{Q}\) over the set \(\mathcal{K}\) is shown in the Table 2. \begin{table}
\begin{tabular}{c c} \hline \hline
**Instance** & **Probability** \\ \hline \(L_{1}=\{s_{1}\}\) & \(q_{1}\) \\ \hline \(L_{2}=\{s_{1},s_{2}\}\) & \(q_{2}\) \\ \hline \(\vdots\) & \(\vdots\) \\ \hline \(L_{k}=\{s_{1},s_{2},\ldots,s_{k}\}\) & \(q_{k}\) \\ \hline \(L_{k+1}=\{s_{1},s_{2},\ldots,s_{k},s_{k+1},s^{\prime}_{k+1}\}\) & \(q_{k+1}\) \\ \hline \(L_{k+2}=\{s_{1},s_{2},\ldots,s_{k},s_{k+1},s_{k+2},s^{\prime}_{k+2}\}\) & \(q_{k+2}\) \\ \hline \(\vdots\) & \(\vdots\) \\ \hline \(L_{k+b}=\{s_{1},s_{2},\ldots,s_{k},s_{k+1},s_{k+2},s_{k+3},\ldots,s_{k+b},s^{ \prime}_{k+b}\}\) & \(q_{k+b}\) \\ \hline \end{tabular}
\end{table} 
Table 10: Probability distribution \(\mathcal{Q}\) over \(\mathcal{K}\). \(\{s_{1},s_{2},\ldots\}\) represents a sequence with jobs from \(s_{1}\) placed first, then from \(s_{2}\), and so on. The arrival times of the jobs are such that the jobs in each of \(L_{1},L_{2},\ldots,L_{k+b}\) are ordered by their arrival times. Then, \(OPT(L_{i})=nD_{min}\alpha^{i-1}\) if \(i\in[k]\) and \(OPT(L_{i})=2 nD_{min}\alpha^{k}\) if \(i\in[k+b]\setminus[k]\). Therefore,  
\[E(OPT(L)) =\sum_{i=1}^{k+b}q_{i}OPT(L_{i})=\sum_{i=1}^{k}q_{k}nD_{min}\alpha ^{i-1}+\sum_{i=1}^{b}q_{k+i}2 nD_{min}\alpha^{k}\] \[=nD_{min}\left(\sum_{i=1}^{k}\left(\frac{1}{\alpha^{i-1}}-\frac{1 }{\alpha^{i}}\right)\alpha^{i-1}+2\right)=nD_{min}\left(2+k\left(1-\frac{1}{ \alpha}\right)\right). \tag{11}\]  
We next find an upper bound on \(E(v_{A}(L))\) for any \(A\in\mathcal{A}_{D}\). Consider an arbitrary deterministic Algorithm \(A\in\mathcal{A}_{D}\). When the instance is \(L_{k+b}(=\{s_{1},s_{2},\ldots,s_{k},s_{k+1},s_{k+2},s_{k+3},\ldots,s_{k+b},s_{ k+b}^{\prime}\})\), let \(n_{i}\) denote the number of jobs accepted by Algorithm \(A\) from the subsequence \(s_{i}\), \(i\in[k+b]\). \(\sum\limits_{i=1}^{k+b}n_{i}\leq n\) holds because each job in the sequence \(\{s_{1},s_{2},\ldots,s_{k},s_{k+1},s_{k+2},s_{k+3},\ldots,s_{k+b}\}\) overlaps with every other job in the same sequence and because only non-overlapping jobs can be assigned to the same server. Since \(A\) is a deterministic online algorithm, it will accept exactly \(n_{1}\) jobs when faced with the instance \(L_{1}(=\{s_{1}\})\). Similarly, when faced with \(L_{2}(=\{s_{1},s_{2}\})\), it will accept \(n_{1}\) jobs from the subsequence \(s_{1}\) and \(n_{2}\) jobs from the subsequence \(s_{2}\). And so on. Therefore, \(v_{A}(L_{i})=\sum\limits_{j=1}^{i}n_{j}\alpha^{j-1}D_{min}\) for \(i\in[k]\).