# The Online Reservation Problem
## 3 Algorithms
### The Deterministic-Selection Algorithm (Algorithm D)
* **Job 3:*
* Job 3 is not admissible to server 1 because it conflicts with job 1 that was previously assigned to server 1. * Job 3 is not admissible to server 2 because it conflicts with job 2 that was previously assigned to server 2. * Job 3 is not admissible to server 3 because duration of job 3 is smaller than the admission threshold of server 3 (\(d_{3}=1.2<\phi(3)\approx 1.236\)). Since there are no servers to which job 3 is admissible, Algorithm \(D\) declines the job. Figure 2: Representation of the instance presented in Table 1.  
* **Job 4:*
* Job 4 is not admissible to server 1 because it conflicts with job 1 that was previously assigned to server 1. * Job 4 is not admissible to server 2 because it conflicts with job 2 that was previously assigned to server 2. * Job 4 is admissible to server 3 because the duration of job 4 is greater than or equal to the admission threshold of server 3 (\(d_{4}=2\geq\phi(3)\approx 1.236\)) and because no jobs were previously assigned to server 3. Because server 3 has the smallest index amongst servers to which job 4 is admissible, Algorithm \(D\) assigns the job to server 3. * **Job 5:*
* Job 5 is admissible to server 1 because duration of job 5 is greater than or equal to admission threshold of server 1 (\(d_{5}=1\geq\phi(1)=1\)) and because job 5 does not conflict with job 1 that was previously assigned to server 1. * Job 5 is admissible to server 2 because the duration of job 5 is greater than or equal to admission threshold of server 2 (\(d_{5}=1\geq\phi(2)=1\)) and because job 5 does not conflict with job 2 that was previously assigned to server 2. * Job 5 is not admissible to server 3 because the duration of job 5 is smaller than the admission threshold of server 3 (\(d_{5}=1<\phi(3)\approx 1.236\)). Because server 1 has the smallest index amongst servers to which job 5 is admissible, Algorithm \(D\) assigns the job to server 1. After all of the decisions, the assignment of jobs to servers is represented in Figure 3, below. Next, we present a result on CR of Algorithm \(D\) in Theorem 4, below. **Theorem 4**. : _The following statements regarding the CR of Algorithm \(D\) are true._  
1. \(r_{D}(1,\Delta)=2\) _if_ \(\Delta=1\)_._
2. \(r_{D}(1,\Delta)=2\Delta+1\) _if_ \(\Delta>1\)_._
3. \(r_{D}(n,\Delta)\leq 3\) _if_ \(\Delta=1\) _and_ \(n\in\mathbb{N}\)_._
4. \(r_{D}(n,\Delta)\leq t\left(n,\Delta\right)+1\) _if_ \(\Delta>1\) _and_ \(n\in\mathbb{N}\)_._  
Sketch of the Proof. : The first three statements follow directly from Theorem 3 because \(\phi(i)=D_{min}\) for all \(i\), and therefore, Algorithm \(D\) is a greedy algorithm for these cases. Proof for the fourth statement is given in Appendix D. Just like Theorem 3, the crux of this proof lies in identifying allocation schemes from the sets of jobs accepted by the algorithm to the offline optimal sets such that Lemma 1 can be applied to prove the proposed upper bound. **Corollary 1**. : \(\lim\limits_{n\to\infty}r_{D}(n,\Delta)\leq 3\ln\Delta+4\)_._  
Figure 3: Assignment of jobs in the instance presented in Table 1 by Algorithm \(D\). The results in the first three statements of Theorem 4 are identical to those that are presented in the first three statements of Theorem 3 because Algorithm \(D\) behaves like a greedy algorithm for those cases. However, by cleverly setting individual thresholds for the servers, Algorithm \(D\) achieves a CR that is \(\mathcal{O}\left(\ln\Delta\right)\) in the limit \(n\to\infty\). In terms of CR, Algorithm \(D\) outperforms any greedy algorithm when \(n\) and \(\Delta\) are sufficiently large. Table 2 is presented in Section 3.3 and it gives values of either the CR or the upper bound on the CR of Algorithm \(D\), as derived in Theorem 4, for some specific \(n\) and \(\Delta\).