# The Online Reservation Problem
## Appendix E Proof of Statements 2 and 4 in Theorem 5  
Proof. : We begin by presenting some notation. \(L\) denotes an arbitrary instance, \(C_{L}\) denotes offline optimal set for \(L\), \(N_{L}(x)\) denotes the total number of jobs with duration equal to \(x\) in \(C_{L}\), \(L_{x}\) denotes the sequence of jobs obtained by removing all jobs with duration strictly less than \(x\) from \(L\), \(C_{L}^{x}\) denotes the subset of jobs obtained by removing all jobs with duration strictly less than \(x\) from \(C_{L}\), \(B_{L}^{x}\) denotes the set of jobs accepted by Algorithm \(R\) from instance \(L\) when sampled threshold is \(x,g(x)\) denotes the total duration of jobs in the set \(B_{L}^{x}\), and \(E\) denotes the set {distinct durations of jobs in \(L\)} \(\cup\{D_{min}\}\) such that \(E=\{x_{1},x_{2},\ldots,x_{k}\}\) and \(D_{min}=x_{1}<x_{2}<\ldots<x_{k}\leq D_{max}\). Define \(p_{1}\doteq\mu(x_{1})\) and \(p_{i}\doteq\mu(x_{i})-\mu(x_{i-1})\) for \(i=2,\ldots,k\). _Statement 2_. : Algorithm \(R\) effectively chooses \(x_{i}\) as threshold with probability \(p_{i}\) for \(i\in[k]\). Consider the run of algorithm when \(R\) chooses \(x_{i}\) as the threshold. Define function \(w_{L}^{x_{i}}:B_{L}^{x_{i}}\times C_{L}^{x_{i}}\mapsto\mathbb{R}\) as follows:  
\[w_{L}^{x_{i}}(b,c)\doteq \begin{cases}d_{c}&\text{if }b\in B_{L}^{x_{i}}\cap C_{L} ^{x_{i}}\text{ and }b\equiv c;\\ x_{i}/3&\text{if }b\text{ and }c\text{ overlap, }b\in B_{L}^{x_{i}}\setminus C_{L}^{x_{i}}\text{, and }c\in C_{L}^{x_{i}} \setminus B_{L}^{x_{i}}\text{; and}\\ 0&\text{otherwise.}\end{cases} \]  
_Claim 11_: \(w_{L}^{x_{i}}\) is an allocation scheme from the set \(B_{L}^{x_{i}}\) to the set \(C_{L}^{x_{i}}\). Proof of Claim 11.: If job \(b\in B_{L}^{x_{i}}\cap C_{L}^{x_{i}}\), then it does not overlap with any other job in \(C_{L}\) except itself (Lemma A1), and therefore, \(\sum\limits_{c\in C_{L}^{x_{i}}}w_{L}^{x_{i}}(b,c)=w_{L}^{x_{i}}(b,b)=d_{b}\). Otherwise if job \(b\in B_{L}^{x_{i}}\setminus C_{L}^{x_{i}}\), the only non-zero allocations from job \(b\) are to jobs in \(C_{L}^{x_{i}}\setminus B_{L}^{x_{i}}\). Let \(M\) be the number of jobs in \(C_{L}^{x_{i}}\setminus B_{L}^{x_{i}}\) that overlap with job \(b\). Therefore, \(\sum\limits_{c\in C_{L}^{x_{i}}}w_{L}^{x_{i}}(b,c)\leq Mx_{i}/3\). If \(M>0\), by Lemma A2, \(d_{b}/M\geq x_{i}/3\implies\sum\limits_{c\in C_{L}^{x_{i}}}w_{L}^{x_{i}}(b,c) \leq d_{b}\). This also holds true if \(M=0\). Therefore, by Definition 1, \(w_{L}^{x_{i}}\) is a valid allocation scheme. Now, any job \(c\in C_{L}^{x_{i}}\) either belongs to \(B_{L}^{x_{i}}\cap C_{L}^{x_{i}}\), in which case \(\sum\limits_{b\in B_{L}^{x_{i}}}w_{L}^{x_{i}}(b,c)\geq w_{L}^{x_{i}}(c,c)=d_{c} \geq x_{i}\geq x_{i}/3\), or belongs to \(C_{L}^{x_{i}}\setminus B_{L}^{x_{i}}\), in which case it is rejected because it overlaps with at least one job in \(B_{L}^{x_{i}}\setminus C_{L}^{x_{i}}\) and hence, \(\sum\limits_{b\in B_{L}^{x_{i}}}w_{L}^{x_{i}}(b,c)\geq x_{i}/3\). Therefore, for any job \(c\in C_{L}^{x_{i}}\), \(\sum\limits_{b\in B_{L}^{x_{i}}}w_{L}^{x_{i}}(b,c)\geq x_{i}/3\). Hence,  
\[g(x_{i})=\sum\limits_{b\in B_{L}^{x_{i}}}d_{b}\geq\sum\limits_{b \in B_{L}^{x_{i}}}\sum\limits_{c\in C_{L}^{x_{i}}}w_{L}^{x_{i}}(b,c)=\sum\limits _{c\in C_{L}^{x_{i}}}\sum\limits_{b\in B_{L}^{x_{i}}}w_{L}^{x_{i}}(b,c)\geq\sum \limits_{c\in C_{L}^{x_{i}}}x_{i}/3=\sum\limits_{j=i}^{k}N(x_{j})x_{i}/3\] \[\implies\frac{\sum\limits_{i=1}^{k}p_{i}g(x_{i})}{OPT(L)}\geq \frac{\sum\limits_{i=1}^{k}p_{i}x_{i}\sum\limits_{j=i}^{k}N(x_{j})}{3 OPT(L)}= \frac{\sum\limits_{i=1}^{k}N(x_{i})\sum\limits_{j=1}^{i}p_{j}x_{j}}{3 OPT(L)}= \frac{\sum\limits_{i=1}^{k}N(x_{i})p_{1}x_{1}+\sum\limits_{i=2}^{k}N(x_{i}) \sum\limits_{j=2}^{i}p_{j}x_{j}}{3 OPT(L)}\]  
For any \(i=2,\ldots,k\), \(\sum\limits_{j=2}^{i}p_{j}x_{j}\geq\int_{x_{1}}^{x_{i}}\frac{d\mu}{dx}xdx=\int _{x_{1}}^{x_{i}}\frac{x\ dx}{x(1+\ln\Delta)}=\frac{x_{i}-x_{1}}{(1+\ln\Delta)}\). Further, \(\sum\limits_{i=1}^{k}p_{i}g(x_{i})=v_{R}(L)\).