Randomized Scheduling for the Online Car-sharing Problem

The car-sharing problem, proposed by Luo, Erlebach and Xu in 2018, mainly focuses on an online model in which there are two locations: 0 and 1, and $k$ total cars. Each request which specifies its pick-up time and pick-up location (among 0 and 1, and the other is the drop-off location) is released in each stage a fixed amount of time before its specified start (i.e. pick-up) time. The time between the booking (i.e. released) time and the start time is enough to move empty cars between 0 and 1 for relocation if they are not used in that stage. The model, called $k$S2L-F, assumes requests in each stage arrive sequentially regardless of the same booking time and the decision (accept or reject) must be made immediately. The goal is to accept as many requests as possible. The model is surprisingly not easy even for only two locations. The previous algorithm achieves a (tight) competitive ratio of $\frac{3}{2}$ only when $k$ is a multiple of three. In this paper, we aim at better algorithms under the assumption that all the requests with the same booking time arrive simultaneously. Indeed, we propose a randomized algorithm which can achieve a competitive ratio of $\frac{4}{3}$ for any value of $k$. In particular, the randomized algorithm can be extended to achieve a ratio of $\frac{2+R}{3}$ if the number of requests in each stage is at most $Rk$, where $R$ is a constant and $1 \le R \le 2$. Both ratios are tight. Our algorithm can also accommodate the original $k$S2L-F without changing its basic structure.