License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2018.50
URN: urn:nbn:de:0030-drops-96325
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9632/
Go to the corresponding LIPIcs Volume Portal

Luo, Kelin ; Erlebach, Thomas ; Xu, Yinfeng

Car-Sharing between Two Locations: Online Scheduling with Two Servers

pdf-format:
LIPIcs-MFCS-2018-50.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{luo_et_al:LIPIcs:2018:9632,
  author =	{Kelin Luo and Thomas Erlebach and Yinfeng Xu},
  title =	{{Car-Sharing between Two Locations: Online Scheduling with Two Servers}},
  booktitle =	{43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018)},
  pages =	{50:1--50:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Igor Potapov and Paul Spirakis and James Worrell},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9632},
  URN =		{urn:nbn:de:0030-drops-96325},
  doi =		{10.4230/LIPIcs.MFCS.2018.50},
  annote =	{Keywords: Car-sharing system, Competitive analysis, On-line scheduling}
}

Keywords: Car-sharing system, Competitive analysis, On-line scheduling
Collection: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Issue Date: 2018
Date of publication: 27.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI