# The Online Reservation Problem
## Appendix D Proof of Statement 4 in Theorem 4  
Before presenting the proof for Theorem 4, we present Lemma A2 that is required for supporting intermediate claims in the proof for Theorem 4 and other subsequent proofs. Lemma A2: _Consider job \(i\) that overlaps with \(k>0\) jobs, none of which overlap with each other. Let \(a\) be the duration of the smallest of the \(k+1\) jobs under consideration, and let \(b\) be the duration of the largest. Then, \(d_{i}/k\geq a/2\) if \(a=b\) and \(d_{i}/k\geq a/3\) if \(a<b\)._  
Proof of Lemma A2. : If \(a=b\), then all the jobs are of the same duration, and therefore, job \(i\) cannot overlap with more than two jobs. Thus, \(k\leq 2\) and \(d_{i}/k\geq a/2\). Otherwise, \(a<b\). When \(k\leq 2\), \(d_{i}\geq a\implies d_{i}/k\geq a/2\geq a/3\). Otherwise, if \(k\geq 3\), then at least \(k-2\) jobs start after \(s_{i}\), the start time of job \(i\), and end before \(s_{i}+d_{i}\), the end time of job \(i\). Therefore, \(d_{i}\geq(k-2)a\implies d_{i}/k\geq\left(\left(k-2\right)a\right)/k\geq a/3\). Proof of Statement 4 in Theorem 4.: Given \(n\) and \(\mathcal{D}\), denote \(t\left(n,\Delta\right)\) by \(t\). Given an instance \(L\), define \(B_{L}\) to be the set of jobs accepted by Algorithm \(D\) and \(C_{L}\) to be the offline optimal set. Define function \(w_{L}:B_{L}\times C_{L}\mapsto\mathbb{R}\) as follows:  
\[w_{L}(b,c)\doteq \begin{cases}d_{c}/(t+1)&\text{if $b\in B_{L}\cap C_{L}$ and $b\equiv c$;}\\ t\phi(i)/((t+1)3n)&\text{if $b$ and $c$ overlap, $b\
ot\equiv c$, $b$ is assigned to server $i$, $\phi(i)\leq d_{c}$;and}\\ 0&\text{otherwise.}\end{cases} \]  
Claim 9: \(w_{L}\) is an allocation scheme from the set \(B_{L}\) to the set \(C_{L}\). Proof of Claim 9.: For any given job \(b\in B_{L}\) that is placed assigned to server \(i\) by Algorithm \(D\), a non-zero allocation from job \(b\) was made to jobs in the set \(C_{L}\setminus\{b\}\) that have duration greater than or equal to \(\phi(i)\), and also to job \(b\) itself if it belongs to \(B_{L}\cap C_{L}\). Set \(C_{L}\) contains jobs that would have been selected if we knew the instance \(L\) upfront, and therefore, the sets \(C_{L}\) and \(C_{L}\setminus\{b\}\) can be partitioned into \(n\) subsets such that each subset consists only of non-overlapping jobs. Let \(D\) denote one of such \(n\) subsets of \(C_{L}\setminus\{b\}\), and let \(M\) be the number of jobs in \(D\) with duration greater than or equal to \(\phi(i)\). Then, \(\sum\limits_{d\in D}w_{L}(b,d)\leq Mt\phi(i)/((t+1)3n)\). If \(M>0\), by Lemma A2, \(d_{b}/M\geq\phi(i)/3\implies\sum\limits_{d\in D}w_{L}(b,d)\leq td_{b}/((t+1)n)\). This also holds true if \(M=0\). Since there are \(n\) subsets in the partition of \(C_{L}\setminus\{b\}\), we have \(\sum\limits_{c\in C_{L}\setminus\{b\}}w_{L}(b,c)\leq td_{b}/(t+1)\). The only other non-zero allocation from job \(b\) could have been to itself if job \(b\in B_{L}\cap C_{L}\), and this allocation is less than or equal to \(d_{b}/(1+t)\). Thus, \(\sum\limits_{c\in C_{L}}w_{L}(b,c)\leq td_{b}/(t+1)+d_{b}/(t+1)=d_{b}\). Therefore, by Definition 1, \(w_{L}\) is an allocation scheme. **Claim 10**: \(d_{c}/\sum\limits_{b\in B_{L}}w_{L}(b,c)\leq t+1\) for any job \(c\) in \(C_{L}\). Proof of Claim 10.: Consider any job \(c\) in \(C_{L}\) and let \(m\) be the largest integer in \([n]\) such that \(\phi(m)\leq d_{c}\). By definition of \(t\), \(d_{c}\leq\phi(m+1)\). If job \(c\) belongs to the set \(C_{L}\setminus B_{L}\), then it was rejected by Algorithm \(D\). Therefore, it must overlap with at least one job assigned to each one of the servers \(1,2,\ldots,m\), where \(I\leq m\leq n\). Therefore, \(\sum\limits_{b\in B_{L}}w_{L}(b,c)\geq\sum\limits_{i=1}^{m}t\phi(i)/((t+1)3n) =\phi(m+1)/(t+1)\geq d_{c}/(t+1)\). Otherwise, if job \(c\) belongs to the set \(C_{L}\cap B_{L}\), \(\sum\limits_{b\in B_{L}}w_{L}(b,c)\geq w_{L}(c,c)=d_{c}/(t+1)\). Therefore, for any job \(c\) in \(C_{L}\), \(d_{c}/\sum\limits_{b\in B_{L}}w_{L}(b,c)\leq t+1\). Since instance \(L\) was arbitrary, by Lemma 1, the result is proved.