@inproceedings{5e17234b956b41b6afe4397ae728c992,
title = "Car-Sharing Problem: Online Scheduling with Flexible Advance Bookings",
abstract = "We study an online scheduling problem that is motivated by applications such as car-sharing for trips among a number of locations. Users submit ride requests, and the scheduler aims to accept as many requests as k servers (cars) could. Each ride request specifies the pick-up time, the pick-up location, and the drop-off location. A request can be submitted at any time during a certain time interval that precedes 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). For the general case in which requests may have arbitrary lengths, L, the ratio of the longest to the shortest request, is an important parameter. We give an algorithm with competitive ratio O(L), where the ratio L is known in advance. It is shown that no -competitive algorithm exists for the fixed booking variant, where. It is also proved that no O(L)-competitive algorithm exists for the variable booking variant.",
keywords = "Car-sharing system, Competitive analysis, General network, Online scheduling",
author = "Haodong Liu and Kelin Luo and Yinfeng Xu and Huili Zhang",
note = "Publisher Copyright: {\textcopyright} 2019, Springer Nature Switzerland AG.; 13th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2019 ; Conference date: 13-12-2019 Through 15-12-2019",
year = "2019",
doi = "10.1007/978-3-030-36412-0\_27",
language = "英语",
isbn = "9783030364113",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer",
pages = "340--351",
editor = "Yingshu Li and Mihaela Cardei and Yan Huang",
booktitle = "Combinatorial Optimization and Applications - 13th International Conference, COCOA 2019, Proceedings",
}