  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.
