# The Online Reservation Problem
## 4 Jobs Arrive at Their Start Times (SORP)  
In this section, we study the special case of the ORP, abbreviated as SORP, where all of the jobs arrive exactly at their start times, and this fact is known upfront to the decision-maker. Although we apply Algorithm \(R\) to the SORP exactly the way we did for the ORP, we modify the server-specific admission thresholds of Algorithm \(D\). This is done to exploit the extra information that is known to the decision-maker that each job will arrive at its start time. We first derive the lower bound on the CR of any algorithm for the SORP (Theorem 6). Subsequently, we analyze CRs of greedy algorithms and Algorithms \(D\) and \(R\) for the SORP (Theorems 7-9). The proofs are very similar to the corresponding derivations for the ORP, and therefore, we omit them here (proofs may be found in [28]). The lower bound on CR of any algorithm and the CRs of the studied algorithms are smaller than those for the ORP because the set of allowed instances for the SORP is a proper subset of those for the ORP. The CR of any algorithm for the SORP is bounded below by \(\underline{r}^{*}(n,\Delta)\doteq\ln\Delta+1\). The following statements regarding the CR of an arbitrary greedy algorithm \(A\) are true. 1. \(r^{*}_{A}(1,\Delta)=1\) if \(\Delta=1\). 2. \(r^{*}_{A}(1,\Delta)=\Delta+1\) if \(\Delta>1\). 3. \(r^{*}_{A}(n,\Delta)\leq 2\) if \(\Delta=1\) and \(n\in\mathbb{N}\). 4. \(\Delta+1\leq r^{*}_{A}(n,\Delta)\leq\Delta+2\) if \(\Delta>1\) and \(n\in\mathbb{N}\). [PERSON] and [PERSON] [10] also prove Statement 2 in Theorem 7, but they do so while using arguments different from ours. We prove all four statements using the common framework of allocation schemes and Lemma 1. Algorithm \(D\) works the same way for the SORP as it does for the ORP; the only difference is that the server thresholds are given by \(\phi^{*}\)'s (defined in Definition 4) instead of \(\phi\)'s. []  
\(\bullet\) \(t^{*}:\mathbb{N}\times[1,\infty)\mapsto\mathbb{R}\) such that \(t^{*}(n,y)\doteq\inf\left\{x\geq 1\ \middle|\ \frac{x}{2n}\middlemiddlemiddlemiddlemiddlemiddlemiddlemiddlemiddlemiddlemiddlemiddle \left(1+\frac{x}{2n}\middlemiddlemiddlemiddlemiddlemiddlemiddlemiddlemiddlemiddle \left(1+\frac{x}{2n}\middlemiddlemiddlemiddlemiddlemiddlemiddlemiddlemiddlemiddle \right)^{n-\lceil\frac{2n}{x}\rceil}\geq y\right\}.\)
* \(I^{*}\doteq\lceil 2n/t^{*}\left(n,\Delta\right)\rceil\). * \(\phi^{*}(i)\doteq\begin{cases}D_{min}&\text{if $i\leq I^{*}$ and $i\in[n+1]$, and}\\ \frac{t^{*}\left(n,\Delta\right)I^{  
The notation that is defined above differs from that in Definition 2 in that each occurrence of 3 in Definition 2 is replaced by 2 here. Theorem 8: _The following statements regarding the CR of Algorithm \(D\) are true._  
1. \(r_{\mathrm{D}}^{*}(1,\Delta)=1\) _if_ \(\Delta=1\)_._
2. \(r_{\mathrm{D}}^{*}(1,\Delta)=\Delta+1\) _if_ \(\Delta>1\)_._
3. \(r_{\mathrm{D}}^{*}(n,\Delta)\leq 2\) _if_ \(\Delta=1\) _and_ \(n\in\mathbb{N}\)_._
4. \(r_{\mathrm{D}}^{*}(n,\Delta)\leq t^{*}\left(n,\Delta\right)+1\) _if_ \(\Delta>1\) _and_ \(n\in\mathbb{N}\)_._  
Corollary 2: \(\lim\limits_{n\to\infty}r_{D}^{*}(n,\Delta)\leq 2\ln\Delta+3\)_._  
Theorem 9: _The following statements regarding the CR of Algorithm \(R\) are true._  
1. \(r_{R}^{*}(1,\Delta)=1\) _if_ \(\Delta=1\)_._
2. \(r_{R}^{*}(1,\Delta)\leq 2\ln\Delta+2\) _if_ \(\Delta>1\)_._
3. \(r_{R}^{*}(n,\Delta)\leq 2\) _if_ \(\Delta=1\) _and_ \(n\in\mathbb{N}\)_._
4. \(r_{R}^{*}(n,\Delta)\leq 3\ln\Delta+3\) _if_ \(\Delta>1\) _and_ \(n\in\mathbb{N}\)_._  
Table 3 gives numerical values of lower bounds and CRs or upper bounds on CRs as derived in this section. We also compare our results with [PERSON] and [PERSON] [10], who study a variant of the SORP in which the servers are available only for specific time intervals. By making these time intervals arbitrarily long, we get back the SORP. [PERSON] and [PERSON] [10] only consider cases where \(\Delta>1\) and propose an \(\mathcal{O}(\ln\Delta)\)-competitive algorithm for it.