# The Online Reservation Problem
## 3 Algorithms
### The Randomized-Selection Algorithm (Algorithm \(R\))  
Algorithm \(R\) also uses a threshold, but the threshold is sampled from a specified distribution. In the beginning, Algorithm \(R\) samples the threshold \(x\) from the distribution with CDF \(\mu\) (defined subsequently in Definition 3). The same threshold \(x\) is then used for all jobs in the instance. Algorithm \(R\) declines all incoming jobs with a duration strictly smaller than the threshold \(x\). Any qualifying job is assigned to the smallest-indexed server with no conflicts, if at least one such server exists. Otherwise, the job is declined. The pseudocode is provided below (Algorithm 2). ```
initialize \(x\) by sampling it from the distribution with CDF \(\mu\);  initialize \(\mathcal{I}=\emptyset\); for every incoming job \(j\) in the instancedo \(\mathcal{I}\leftarrow\{i\in[n]\), such that job \(j\) does not conflict with any previously-accepted job of server \(i\}\); if\(\mathcal{I}\
eq\emptyset\) and \(d_{j}\geq x\)then  assign job \(j\) to server \(\min\{i\) such that \(i\in\mathcal{I}\}\); else  decline job \(j\);  end if  end for
```  
**Algorithm 2**Pseudocode for Algorithm \(R\). The idea behind the threshold in Algorithm \(R\) is the same as that in Algorithm \(D\): to increase the likelihood that some longer duration jobs will be accepted by turning away small jobs and thereby overcoming a shortcoming of the greedy algorithms. **Definition 3**. : _CDF \(\mu:\mathbb{R}\mapsto[0,1]\), such that_  
\[\mu(x)\doteq \begin{cases}0&\text{if $x<D_{min}$},\\ \frac{1+\ln(x/D_{min})}{1+\ln\Delta}&\text{if $x\in[D_{min},D_{max}]$, and}\\ 1&\text{otherwise.}\end{cases} \]  
To further illustrate how Algorithm \(R\) works, we consider a numerical example where \(D_{min}=1\), \(D_{max}=2\), and \(n=3\). Therefore, \(\Delta=2\). We consider the same instance that was presented in Table 1 and Figure 2. Algorithm \(R\) first samples threshold \(x\) from the distribution with CDF \(\mu\). For the purpose of this example, we will assume that the sampled value is \(1.1\). Note that the decisions would be different if the sampling resulted in a different value of \(x\). Anyhow, for \(x=1.1\), Algorithm \(R\) makes decisions as follows:  
* **Job 1:** Because the duration of job 1 is less than threshold \(x\) (\(d_{1}=1<x=1.1\)), Algorithm \(R\) declines the job. * **Job 2:** The duration of job 2 is greater than threshold \(x\) (\(d_{2}=1.2\geq x=1.1\)). Further, none of the servers have any previously-accepted jobs that conflict with job 2. Because server 1 has the smallest index amongst these servers, Algorithm \(R\) assigns the job to server 1. * **Job 3:** The duration of job 3 is greater than threshold \(x\) (\(d_{3}=1.2\geq x=1.1\)). Further, only servers 2 and 3 do not have any previously-accepted jobs that conflict with job 3. Because server 2 has the smallest index amongst these servers, Algorithm \(R\) assigns the job to server 2. * **Job 4:** The duration of job 4 is greater than threshold \(x\) (\(d_{4}=2\geq x=1.1\)). Further, only server 3 does not have any previously-accepted jobs that conflict with job 4. Therefore, Algorithm \(R\) assigns the job to server 3. * **Job 5:** Because the duration of job 5 is less than threshold \(x\) (\(d_{5}=1<x=1.1\)), Algorithm \(R\) declines the job. After all of the decisions, the assignment of jobs to servers is represented in Figure 4, below. Next, we present a result on CR of Algorithm \(R\) in Theorem 5, below. Theorem 5: _The following statements regarding the CR of Algorithm \(R\) are true._  
1. \(r_{R}(1,\Delta)=2\) _if_ \(\Delta=1\)_._
2. \(r_{R}(1,\Delta)\leq 3\ln\Delta+3\) _if_ \(\Delta>1\)_._
3. \(r_{R}(n,\Delta)\leq 3\) _if_ \(\Delta=1\) _and_ \(n\in\mathbb{N}\)_._
4. \(r_{R}(n,\Delta)\leq 4\ln\Delta+4\) _if_ \(\Delta>1\) _and_ \(n\in\mathbb{N}\)_._  
Sketch of the Proof. : Statements 1 and 3 follow directly from Theorem 3 because the sampled threshold is equal to \(D_{min}\) with probability 1, and therefore, Algorithm \(R\) is a greedy algorithm for these cases.