# The Online Reservation Problem
## 1 Introduction
### Related Literature
First, they show that multiple different sequences \(z(1),z(2),\ldots\) can be used for constructing randomized algorithms for the problem if \(\sum\limits_{i=1}^{\infty}1/z(i)\) converges, and that the resulting algorithm will be \(\mathcal{O}\left(\ln\left(z\left(\Delta\right)\right)\right)\)-competitive. Second, the authors generalize the results to include the multiple server case. Unlike the problems that were studied by [PERSON] and [PERSON] [23] and [PERSON] et al. [25], \(D_{min}\) and \(D_{max}\) are known in the case of sharing economy platforms. Therefore, we exploit this information to obtain better CRs. [PERSON] et al. [24] consider the online scheduling of continuous media streams. This is identical to the single server case of the SORP, except that jobs now only demand a portion of the bandwidth of the server. They prove that no algorithm can be better than \(\mathcal{O}\left(\ln\Delta/(1-\gamma)\right)\)-competitive, where \(\gamma\) is the maximum fractional bandwidth that any job can demand. They also propose an algorithm that has CR within a constant factor of \(\ln\Delta\) if \(\gamma<1/\left\lceil\ln\Delta\right\rceil\). In the case of rental platforms, the customer must demand at least one unit of resource and, therefore, the fractional bandwidth assumption of [24] does not hold. One might be tempted to think that the multiple server case of SORP is equivalent to the problem that was studied by [PERSON] et al. [24]. However, in a rental platform setting, the customer must be assigned a unique resource (such as a room or a car) throughout the duration of the contract. The formulation studied by [PERSON] et al. [24] fails to impose such a requirement and, hence, the supposed equivalence does not hold. Finally, we would like to mention that [PERSON] and [PERSON] [26] study an online version of a revenue management problem that has many similarities with the ORP. In their formulation, each job is characterized by a fare and a maximum of \(n\) jobs can be accepted. The problem studied by [PERSON] and [PERSON] [26] can be thought of as consisting of those instances in which the start times of all the jobs are identical from the perspective of the framework that we established for the ORP in Section 1.1. Therefore, each job in an arbitrary instance of the problem conflicts with every other job in the same instance. Additionally, because of this, only \(n\) jobs can be accepted at most. Furthermore, the fares in the formulation by [PERSON] and [PERSON] [26] can be thought of as job durations in the ORP. Therefore, the formulation studied in [26] is equivalent to a special case of the ORP where the set of allowed instances is a proper subset of those for the ORP. [PERSON] and [PERSON] [26] study various versions of their problem that differ based on the set of the possible fares and based on whether a job must be completely accepted (discrete version) or partial acceptance is allowed (continuous version). Like the discrete version, jobs must be either accepted or declined entirely in the ORP. However, partial acceptance of jobs in the continuous version studied by [26] can be considered to be equivalent to an owner making accept/decline decisions that are based on weighted coin flips. [PERSON] and [PERSON] [26] propose threshold-based algorithms for the various versions that they study and prove optimality for some of of them. Most notably, they prove that no algorithm for the continuous version of their problem that allows jobs to have any fare in the set \([D_{min},D_{max}]\) can have a CR better than \(1+\ln\Delta\). They also present an algorithm that achieves CR that is exactly equal to the lower bound. Note that one cannot directly use the algorithms or other results from [26] for the ORP because the set of allowed instances for the formulation studied in [26] is a proper subset of those for the ORP. We complement the work of [PERSON] and [PERSON] [26] by studying the ORP that does not constrain the job start times to be identical.