# The Online Reservation Problem
## 1 Introduction
### The Problem Statement  
An instance \(L\) of the ORP is a non-empty finite sequence of requests or jobs. Each job \(i\) in \(L\) has three attributes: arrival time \(a_{i}\geq 0\), start time \(s_{i}\) (\(\geq a_{i}\)), and length (or duration) \(d_{i}\). Let \(D_{min}>0\) and \(D_{max}<\infty\) be the contract-length limits. We constrain \(L\) to belong to a set \(\mathcal{L}(\mathcal{D})\), where \(\mathcal{D}\doteq[D_{min},D_{max}]\). What this means is that, while \(L\) can consist of an arbitrary number of jobs with arbitrary arrival and start times, the length of each job must belong to the interval \([D_{min},D_{max}]\). We also define \(\Delta\doteq D_{max}/D_{min}\). Let \(n\) denote the maximum number of concurrently available identical resources or servers, indexed \(1,2,\ldots,n\). Each server can only process one job at a time. Jobs in \(L\) arrive one at a time and the attributes of each job are revealed only upon its arrival. As soon as a job arrives, the owner must immediately assign the job to one of the servers (resources) or decline it, only knowing that the length of any job that may arrive later will be in \(\mathcal{D}\). Once assigned, a job cannot be reassigned to other servers or be preempted. Similarly, overlapping (or clashing or conflicting) jobs may not be assigned to the same server, i.e., jobs \(i\) and \(j\) with \(s_{i}\leq s_{j}\) and \(s_{i}+d_{i}>s_{j}\) cannot be assigned to the same server. Given job \(i\), we say that server \(j\) has no conflicts if no job already assigned to server \(j\) clashes with job \(i\). Without a loss of generality, we set the unit rent equal to \(1\). Therefore, the owner receives a reward that is equal to the duration of the job if it is assigned to one of the \(n\) servers and zero otherwise. Declined jobs are lost. We say that job-\(i\)\(\equiv\) job-\(j\), i.e., \(i\) and \(j\) represent the same job, if \(a_{i}=a_{j}\), \(s_{i}=s_{j}\), and \(d_{i}=d_{j}\)Given \(L\), let \(OPT(L)\) denote the total value of jobs in an offline optimal set, which is an optimal set of jobs that would be accepted if \(L\) was known entirely in advance. Let \(A\) denote an arbitrary algorithm in the set \(\mathcal{A}\), where \(\mathcal{A}\) is the set of algorithms that, upon arrival of a job, either immediately assign it to one of the servers with no conflicts, or decline it, based only on the characteristics of the previously-arrived jobs, the past assign/decline decisions, the number of servers \(n\), and the set \(\mathcal{D}\). Given \(A\), let \(v_{A}(L)\) denote the expected total value of jobs accepted by \(A\) for the problem instance \(L\). Given this notation, the relative performance of \(A\) for instance \(L\) is defined as \(OPT(L)/v_{A}(L)\) and the competitive ratio (CR) of \(A\) is defined as  
\[r_{A}(n,\Delta)\doteq\sup_{L\in\mathcal{L}(\mathcal{D})}\frac{OPT(L)}{v_{A}(L)}.\]  
Given \(n\) and \(\Delta\), which we will sometimes refer to as the parameters of the problem, our objective is to find an \(A^{\prime}\) such that \(r_{A^{\prime}}\leq r_{A}\) for every \(A\in\mathcal{A}\). Additionally, we say that Algorithm \(A\) is \(c\)-competitive if \(c\geq r_{A}\). Note that, although \(OPT(L)>0\), for any \(L\), \(v_{A}(L)\) can possibly be equal to \(0\) for some \(A\) and \(L\). To handle such cases, throughout the paper, we will assume that \(a/0=\infty\) for any \(a\in\mathbb{R}\setminus\{0\}\) and \(\infty>b\) for any \(b\in\mathbb{R}\). We also study a special case, which is abbreviated as SORP (special ORP). The difference between the ORP and the SORP is that \(s_{i}=a_{i}\) for each \(i\) in the latter (see Figure 1). Such scenarios fit operations at platforms such as Uber and Lyft, and in problems that deal with the assignment of open jobs to reserve drivers in transit operations [10]. We use \(\mathcal{L}^{*}(\mathcal{D})\) to denote the set of all possible non-empty finite sequences in which jobs arrive at their start times.