LIPIcs-MFCS-2018-50.pdf (473.1 kB)
Download fileCar-Sharing between Two Locations: Online Scheduling with Two Servers
conference contribution
posted on 2018-07-30, 10:56 authored by Kelin Luo, Thomas Erlebach, Yinfeng XuIn this paper, we consider an on-line scheduling problem that is motivated by applications such
as car sharing, in which users submit ride requests, and the scheduler aims to accept requests of
maximum total profit using two servers (cars). Each ride request specifies the pick-up time and
the pick-up location (among two locations, with the other location being the destination). The
length of the time interval between the submission of a request (booking time) and the pick-up
time is fixed. The scheduler has to decide whether or not to accept a request immediately at the
time when the request is submitted. We present lower bounds on the competitive ratio for this
problem and propose a smart greedy algorithm that achieves the best possible competitive ratio.
History
Citation
Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, 2018, pp. 50:1-50:14 (14)Author affiliation
/Organisation/COLLEGE OF SCIENCE AND ENGINEERING/Department of InformaticsSource
43rd International Symposium on Mathematical Foundations of Computer Science. MFCS 2018, LiverpoolVersion
- VoR (Version of Record)