Car-sharing between two locations: online scheduling with two servers

Kelin Luo, Thomas Erlebach, Yinfeng Xu

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

7 Citations (Scopus)
23 Downloads (Pure)

Abstract

In 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.

Original languageEnglish
Title of host publication43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018
EditorsIgor Potapov, James Worrell, Paul Spirakis
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages14
ISBN (Print)9783959770866
DOIs
Publication statusPublished - 1 Aug 2018
Externally publishedYes
Event43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018 - Liverpool, United Kingdom
Duration: 27 Aug 201831 Aug 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume117
ISSN (Print)1868-8969

Conference

Conference43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018
Country/TerritoryUnited Kingdom
CityLiverpool
Period27/08/1831/08/18

Keywords

  • Car-sharing system
  • Competitive analysis
  • On-line scheduling

Fingerprint

Dive into the research topics of 'Car-sharing between two locations: online scheduling with two servers'. Together they form a unique fingerprint.

Cite this