TY - GEN
T1 - Algorithms for Online Car-Sharing Problem
AU - Guo, Xiangyu
AU - Luo, Kelin
N1 - Publisher Copyright: © 2022, Springer Nature Switzerland AG.
PY - 2022
Y1 - 2022
N2 - In the online car-sharing (a.k.a. ride-sharing) problem, we are given a set of m available car, and n requests arrive sequentially in T periods, in which each request consists of a pick-up location and a drop-off location. In each period, we must immediately and irrevocably assign free cars to serve arrived requests, such that two requests share one car. The goal is to find an online algorithm to process all requests while minimizing the total travel distance of cars. We give the first algorithm for this problem under the adversarial model and the random arrival model. For the adversarial model, we give a 2 T+ 1 / 2 -competitive algorithm, then we show this can be further improved to 2T-competitive by a carefully designed edge cost function. This almost matches the known 2 T- 1 lower bound in this model. For the random arrival model, our algorithm is 3 HT- 1 / 2 + o(1 ) -competitive, where HT is the T-th harmonic number. All the above three results are based on one single algorithm that runs in O(n3) time.
AB - In the online car-sharing (a.k.a. ride-sharing) problem, we are given a set of m available car, and n requests arrive sequentially in T periods, in which each request consists of a pick-up location and a drop-off location. In each period, we must immediately and irrevocably assign free cars to serve arrived requests, such that two requests share one car. The goal is to find an online algorithm to process all requests while minimizing the total travel distance of cars. We give the first algorithm for this problem under the adversarial model and the random arrival model. For the adversarial model, we give a 2 T+ 1 / 2 -competitive algorithm, then we show this can be further improved to 2T-competitive by a carefully designed edge cost function. This almost matches the known 2 T- 1 lower bound in this model. For the random arrival model, our algorithm is 3 HT- 1 / 2 + o(1 ) -competitive, where HT is the T-th harmonic number. All the above three results are based on one single algorithm that runs in O(n3) time.
KW - Car-sharing
KW - Competitive analysis
KW - Online matching
UR - https://www.scopus.com/pages/publications/85124656691
U2 - 10.1007/978-3-030-95018-7_18
DO - 10.1007/978-3-030-95018-7_18
M3 - Conference contribution
SN - 9783030950170
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 224
EP - 236
BT - Algorithms and Discrete Applied Mathematics - 8th International Conference, CALDAM 2022, Proceedings
A2 - Balachandran, Niranjan
A2 - Inkulu, R.
PB - Springer Science and Business Media Deutschland GmbH
T2 - 8th International Conference on Algorithms and Discrete Applied Mathematics, CALDAM 2022
Y2 - 10 February 2022 through 12 February 2022
ER -