Car-sharing on a star network: on-line scheduling with k servers

Kelin Luo, Thomas Erlebach, Yinfeng Xu

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

2 Citaten (Scopus)
6 Downloads (Pure)

Samenvatting

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 Lt for some L ≥ 1. We give an algorithm with competitive ratio O(log L) if the number of servers is at least dlog Le. For both variants, we prove matching lower bounds on the competitive ratio of any deterministic on-line algorithm.

Originele taal-2Engels
Titel36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019
RedacteurenRolf Niedermeier, Christophe Paul
UitgeverijSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Aantal pagina's14
ISBN van elektronische versie9783959771009
DOI's
StatusGepubliceerd - 1 mrt 2019
Extern gepubliceerdJa
Evenement36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019 - Berlin, Duitsland
Duur: 13 mrt 201916 mrt 2019

Publicatie series

NaamLeibniz International Proceedings in Informatics, LIPIcs
Volume126
ISSN van geprinte versie1868-8969

Congres

Congres36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019
LandDuitsland
StadBerlin
Periode13/03/1916/03/19

Vingerafdruk Duik in de onderzoeksthema's van 'Car-sharing on a star network: on-line scheduling with k servers'. Samen vormen ze een unieke vingerafdruk.

Citeer dit