posted on 2019-06-10, 14:42authored byKelin Luo, Thomas Erlebach, Yinfeng Xu
We study an on-line scheduling problem that is motivated by applications such as car-sharing for trips between an airport and a group of hotels. Users submit ride requests, and the scheduler aims to accept requests of maximum total profit using k servers (cars). Each ride request specifies the pick-up time, the pick-up location, and the drop-off location, where one of the two locations must be the airport. A request must be submitted a fixed amount of time before the pick-up time. The scheduler has to decide whether or not to accept a request immediately at the time when the request is submitted (booking time). In the unit travel time variant, the travel time between the airport and any hotel is a fixed value t. We give a 2-competitive algorithm for the case in which the booking interval (pick-up time minus booking time) is at least t and the number of servers is even. In the arbitrary travel time variant, the travel time between the airport and a hotel may have arbitrary length between t and L*t for some L >= 1. We give an algorithm with competitive ratio O(log L) if the number of servers is at least log L. For both variants, we prove matching lower bounds on the competitive ratio of any deterministic on-line algorithm.
Funding
This work was partially supported by the China Postdoctoral Science Foundation
(Grant No. 2016M592811), and the China Scholarship Council (Grant No. 201706280058).
History
Citation
Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), 2019, 126, pp. 47:1-47:14
Author affiliation
/Organisation/COLLEGE OF SCIENCE AND ENGINEERING/Department of Informatics
Source
36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), Berlin
Version
VoR (Version of Record)
Published in
Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)