# The Online Reservation Problem
## 1 Introduction
### Related Literature  
Several studies that analyze online scheduling problems that are similar to the ORP assume that some distributional information on job arrivals and/or durations is available [12; 13; 14]. Because the focus in these studies is on exploiting the distributional information, we do not review them. Instead we focus on those paper related to the ORP that do not assume availability of such information and seek algorithms with the best CR. Amongst these, there are numerous papers that allow for the preemption of already accepted jobs. Papers in this stream propose algorithms for problems with a variety of different features and analyze the CRs of proposed algorithms; see [15; 16; 17; 18; 19; 20]. Preemption is not allowed in our setting, and therefore, we focus on papers that do not allow preemption. Finally, although [PERSON] and [PERSON] [21] analyze a generic online packing problem that does not allow preemption using the primal-dual framework, it is not possible to express ORP or SORP as their online packing formulation. Therefore, we do not discuss [21] either. [PERSON] and [PERSON] [22] analyze online seat reservations for a train that stops at \(k\) stations. They study two scenarios, first where all of the tickets yield the same reward, and second where the reward from a ticket is proportional to the number of stops in the journey. If we think of tickets as jobs and seats as servers, it is easy to see the connection between the latter scenario and the ORP. [PERSON] and [PERSON] [22] only consider greedy algorithms. Instead of \"greedy\", they use the term \"fair\" for such algorithms. They prove that CR of any greedy deterministic algorithm is \(\Theta(k)\), which means that there exist real numbers \(c_{1},c_{2}>0\) and integer \(k_{0}>0\) such that \(c_{1}k\leq CR\leq c_{2}k\) for all \(k\geq k_{0}\). By plugging in \(D_{min}=1\) and \(D_{max}=k-1\) in the expressions for CRs of greedy algorithms for the ORP, we find that they are indeed \(\Theta(k)\)-competitive. However, since we do not limit ourselves to greedy algorithms, we are able to achieve smaller CRs. Moreover, [PERSON] and [PERSON] [22]'s formulation allows for jobs to have durations only in the integer set \(\{1,2,\ldots,k-1\}\), whereas the ORP allows durations to belong to the interval \([1,k-1]\). Some other papers, e.g., [10; 23; 24], are similar to the SORP in the sense that they assume that jobs arrive exactly at their start times. We cannot use the algorithms or other results from these papers for the ORP because the set of allowed instances for the SORP is a proper subset of those for the ORP. However, our approach for the ORP can be utilized to solve the SORP. We will show in Section 4 that we can tweak our ORP algorithms to achieve even smaller CRs for the SORP. [PERSON] and [PERSON] [10] study the multi-processor online fixed job scheduling problem for reserve driver scheduling. Their problem is identical to the SORP, except that the servers in their version are only available for specific time intervals, which model driver shifts. They propose a randomized algorithm for their problem that is \(\mathcal{O}\left(\ln\Delta\right)\)-competitive. One of our algorithms is also \(\mathcal{O}\left(\ln\Delta\right)\)-competitive. Furthermore, the numerical values of the upper bounds on CRs of our algorithms are much smaller than that of [PERSON] and [PERSON] [10]'s algorithm. [PERSON] and [PERSON] [23] study a problem that is identical to the SORP with a single server, except that \(D_{max}\) and \(D_{min}\) are not known. They show that no algorithm can have a CR that is \(\mathcal{O}\left(\ln\Delta\right)\) or better. They also propose an algorithm that is \(\mathcal{O}\left(\ln\Delta\right)^{1+\varepsilon}\)-competitive, where \(\varepsilon\) is any positive real number. This randomized algorithm relies on a specific converging sequence of coin-flip probabilities. [PERSON] et al. [25] extend these results in two ways.