# The Online Reservation Problem
## Appendix C Proof of Theorem 3
Since instance \(L\) was arbitrary, by Lemma 1 and Theorem 2, the result is proved. _Statement 2._ Given instance \(L\), define function \(w_{L}:B_{L}\times C_{L}\mapsto\mathbb{R}\) as follows:  
\[w_{L}(b,c)\doteq \begin{cases}D_{min}&\text{if $b\in B_{L}\cap C_{L}$ and $b\equiv c$;}\\ \dfrac{d_{c}}{2\Delta+1}&\text{if $b$ and $c$ overlap, $b\in B_{L}\setminus C_{L}$, and $c\in C_{L}\setminus B_{L}$; and}\\ 0&\text{otherwise.}\end{cases} \]  
_Claim 3:_\(w_{L}\) is an allocation scheme from the set \(B_{L}\) to the set \(C_{L}\). Proof of Claim 3.: If job \(b\in B_{L}\cap C_{L}\), then it does not overlap with any other job in \(C_{L}\) except itself (Lemma A1), and therefore, \(\sum\limits_{c\in C_{L}}w_{L}(b,c)=w_{L}(b,b)=D_{min}\leq d_{b}\). Otherwise if job \(b\in B_{L}\setminus C_{L}\), the total duration of jobs in \(C_{L}\) that can overlap with it is strictly less than \(2D_{max}+d_{b}\) (Lemma A1), and therefore, \(\sum\limits_{c\in C_{L}}w_{L}(b,c)<\dfrac{2D_{max}+d_{b}}{2\Delta+1}=\dfrac{2D _{max}+d_{b}}{2D_{max}+D_{min}}D_{min}\leq\dfrac{d_{b}}{D_{min}}D_{min}=d_{b}\). Therefore, by Definition 1, \(w_{L}\) is a valid allocation scheme. _Claim 4:_\(d_{c}/\sum\limits_{b\in B_{L}}w_{L}(b,c)\leq 2\Delta+1\) for any job \(c\) in \(C_{L}\). Proof of Claim 4.: If job \(c\in C_{L}\cap B_{L}\), then it does not overlap with any other job in \(B_{L}\) except itself (Lemma A1), and therefore, \(d_{c}/\sum\limits_{b\in B_{L}}w_{L}(b,c)=d_{c}/w_{L}(c,c)=D_{min}/D_{min}\leq 2 \Delta+1\). Otherwise if job \(c\in C_{L}\setminus B_{L}\), it must overlap with at least one job in \(B_{L}\setminus C_{L}\) because Algorithm \(A\) could not have declined job \(c\) otherwise. Therefore, \(d_{c}/\sum\limits_{b\in B_{L}}w_{L}(b,c)\leq d_{c}/\left(\frac{d_{c}}{2\Delta+ 1}\right)=2\Delta+1\). Since instance \(L\) was arbitrary, by Lemma 1, \(r_{A}\leq 2\Delta+1\). We will now prove a matching lower bound. Let \(\beta>0\) be arbitrarily large and \(\epsilon>0\) be arbitrarily small. Consider instance \(L\) in which the jobs arrive in following sequence: \((\beta,D_{min}+2\epsilon),(\beta+\epsilon-D_{max},D_{max}),(\beta+\epsilon,D_{ min}),(\beta+\epsilon+D_{min},D_{max})\). Each 2-tuple represents a job, with first value being the start time and the second being the duration. Then, \(OPT(L)/v_{A}(L)=(D_{min}+2D_{max})/(D_{min}+2\epsilon)\). Therefore, \((D_{min}+2D_{max})/(D_{min}+2\epsilon)\leq r_{A}\). Since \(\epsilon\) was arbitrary, this inequality holds for every \(\epsilon\), letting \(\epsilon\to 0\) gives us the matching lower bound, \(2\Delta+1\leq r_{A}\). _Statement 3._ Given instance \(L\), define function \(w_{L}:B_{L}\times C_{L}\mapsto\mathbb{R}\) as follows:  
\[w_{L}(b,c)\doteq \begin{cases}D_{min}/3&\text{if $b\in B_{L}\cap C_{L}$ and $b\equiv c$;}\\ D_{min}/(3n)&\text{if $b\text{ and $c$ overlap, and $b\
ot\equiv c$;and}$}\\ 0&\text{otherwise.}\end{cases} \]  
_Claim 5:_\(w_{L}\) is an allocation scheme from the set \(B_{L}\) to the set \(C_{L}\). Proof of Claim 5.: For any job \(b\) in \(B_{L}\), at most \(2n\) jobs from \(C_{L}\setminus\{b\}\) can overlap with it (Lemma A1), and therefore, \(\sum\limits_{c\in C_{L}\setminus\{b\}}w_{L}(b,c)\leq 2 nD_{min}/3n=2D_{min}/3\). Further, if \(b\in B_{L}\cap C_{L}\), \(w_{L}(b,b)=D_{min}/3\). Therefore, for any job \(b\in B_{L}\), \(\sum\limits_{c\in C_{L}}w_{L}(b,c)\leq 2D_{min}/3+D_{min}/3=D_{min}=d_{b}\). Hence, by Definition 1, \(w_{L}\) is an allocation scheme. _Claim 6:_\(d_{c}/\sum\limits_{b\in B_{L}}w_{L}(b,c)\leq 3\) for any job \(c\) in \(C_{L}\). Proof of Claim 6.: If job \(c\in C_{L}\cap B_{L}\), then \(d_{c}/\sum\limits_{b\in B_{L}}w_{L}(b,c)\leq d_{c}/w_{L}(c,c)=D_{min}/\left(D_{ min}/3\right)=3\). Otherwise if job \(c\in C_{L}\setminus B_{L}\), it must overlap with at least \(n\) jobs in \(B_{L}\) because Algorithm \(A\) could not have declined job \(c\) otherwise. Therefore, \(d_{c}/\sum\limits_{b\in B_{L}}w_{L}(b,c)\leq D_{min}/\left(nD_{min}/(3n) \right)=3\). Since instance \(L\) was arbitrary, by Lemma 1, the result is proved.