2026-07-25T13:34:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10290 2024-03-06T10:45:44Z ddc:004 open_access

Car-Sharing on a Star Network: On-Line Scheduling with k Servers Luo, Kelin Erlebach, Thomas Xu, Yinfeng Car-Sharing System On-Line Scheduling Competitive Analysis Star Network 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 ceil[log L]. For both variants, we prove matching lower bounds on the competitive ratio of any deterministic on-line algorithm. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kelin Luo and Thomas Erlebach and Yinfeng Xu 2019 Is Part Of LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2019.51 urn:nbn:de:0030-drops-102907 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.51 eng https://creativecommons.org/licenses/by/3.0/legalcode