# The Online Reservation Problem
## Appendix C Proof of Theorem 3  
Before proceeding with the proof for Theorem 3, we present Lemma A1 that we will use to substantiate some intermediate claims in the theorem's proof. **Lemma A1**. : _Given an instance \(L\), define \(B_{L}\) be the set of jobs accepted by Algorithm \(A\) and \(C_{L}\) be an offline optimal set. Then, following statements hold true:_  
1. _If_ \(n=1\)_, any job_ \(b\in B_{L}\cap C_{L}\) _does not overlap with any other job in_ \(C_{L}\) _except itself. Also, any job_ \(c\in C_{L}\cap B_{L}\) _does not overlap with any other job in_ \(B_{L}\) _except itself._
2. _If_ \(D_{max}=D_{min}\)_, then any job_ \(b\in B_{L}\) _overlaps with at most_ \(2n\) _jobs in the set_ \(C_{L}\)_._
3. _If_ \(D_{max}>D_{min}\)_, then for any job_ \(b\in B_{L}\)_, the jobs in_ \(C_{L}\) _that overlap with job_ \(b\) _have total duration strictly less than_ \(n\left(2D_{max}+d_{b}\right)\)_._  
Proof of Lemma A1. : _Statement 1._ Follows directly from the fact that set \(B_{L}\) contains only non-overlapping jobs and that the same holds for set \(C_{L}\). _Statement 2._ Set \(C_{L}\) contains jobs that would have been selected if we knew the instance \(L\) upfront, and therefore, it can be partitioned into \(n\) subsets such that each subset consists only of non-overlapping jobs. Now, any job in \(B_{L}\) can overlap with at most \(2\) jobs in any one of these subsets. Therefore, any job \(b\in B_{L}\) overlaps with at most \(2n\) jobs in the set \(C_{L}\). _Statement 3._ Set \(C_{L}\) contains jobs that would have been selected if we knew the instance \(L\) upfront, and therefore, it can be partitioned into \(n\) subsets such that each subset consists only of non-overlappingjobs. Now, for any job \(b\in B_{L}\), the total duration of jobs that overlap with job \(b\) in any one of the subsets must be strictly less than \(2D_{max}+d_{b}\). Therefore, the total duration of jobs in \(C_{L}\) that overlap with a given job \(b\in B_{L}\) is strictly less than \(n\left(2D_{max}+d_{b}\right)\). Proof of Theorem 3.: We begin by noting that although other well-known arguments may be used to prove the result for some specific values of \(n\) and \(\Delta\), but we prove all four statements using the common framework of allocation schemes and Lemma 1. Given an instance \(L\), define \(B_{L}\) to be the set of jobs accepted by Algorithm \(A\) and \(C_{L}\) to be the offline optimal set. Then, the individual proofs of the four statements are as follows. _Statement 1._ 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$;}\\ D_{min}/2&\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 1:_\(w_{L}\) is an allocation scheme from the set \(B_{L}\) to the set \(C_{L}\). Proof of Claim 1.: 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}\), it cannot overlap with more than 2 jobs in \(C_{L}\setminus B_{L}\) (Lemma A1), and therefore, \(\sum\limits_{c\in C_{L}}w_{L}(b,c)\leq 2\left(D_{min}/2\right)=D_{min}\leq d_{b}\). Therefore, by Definition 1, \(w_{L}\) is a valid allocation scheme. _Claim 2:_\(d_{c}/\sum\limits_{b\in B_{L}}w_{L}(b,c)\leq 2\) for any job \(c\) in \(C_{L}\). Proof of Claim 2.: 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)=w_{L}(c,c)/d_{c}=D_{min}/D_{min}\leq 2\). 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(D_{min}/2\right)=2\).