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

Kelin Luo; Thomas Erlebach; Yinfeng Xu

doi:10.4230/LIPIcs.MFCS.2018.50

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

Kelin Luo
, Thomas Erlebach
, Yinfeng Xu

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

9 Citations (Scopus)

50 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 language	English
Title of host publication	43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018
Editors	Igor Potapov, James Worrell, Paul Spirakis
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages	14
ISBN (Print)	9783959770866
DOIs	https://doi.org/10.4230/LIPIcs.MFCS.2018.50
Publication status	Published - 1 Aug 2018
Externally published	Yes
Event	43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018 - Liverpool, United Kingdom Duration: 27 Aug 2018 → 31 Aug 2018

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	117
ISSN (Print)	1868-8969

Conference

Conference	43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018
Country/Territory	United Kingdom
City	Liverpool
Period	27/08/18 → 31/08/18

Funding

This work was partially supported by the China Postdoctoral Science Foundation (Grant No. 2016M592811), and the China Scholarship Council (Grant No. 201706280058).

Keywords

Car-sharing system
Competitive analysis
On-line scheduling

Access to Document

10.4230/LIPIcs.MFCS.2018.50

publishers versionFinal published version, 473 KB

Cite this

Luo, K., Erlebach, T., & Xu, Y. (2018). Car-sharing between two locations: online scheduling with two servers. In I. Potapov, J. Worrell, & P. Spirakis (Eds.), 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018 Article 50 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 117). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.MFCS.2018.50

Luo, Kelin ; Erlebach, Thomas ; Xu, Yinfeng. / Car-sharing between two locations : online scheduling with two servers. 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018. editor / Igor Potapov ; James Worrell ; Paul Spirakis. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. (Leibniz International Proceedings in Informatics, LIPIcs).

@inproceedings{ac0c9c9cef014f3c9ec933beb828bfc0,

title = "Car-sharing between two locations: online scheduling with two servers",

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.",

keywords = "Car-sharing system, Competitive analysis, On-line scheduling",

author = "Kelin Luo and Thomas Erlebach and Yinfeng Xu",

year = "2018",

month = aug,

day = "1",

doi = "10.4230/LIPIcs.MFCS.2018.50",

language = "English",

isbn = "9783959770866",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

editor = "Igor Potapov and James Worrell and Paul Spirakis",

booktitle = "43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018",

note = "43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018 ; Conference date: 27-08-2018 Through 31-08-2018",

}

Luo, K, Erlebach, T & Xu, Y 2018, Car-sharing between two locations: online scheduling with two servers. in I Potapov, J Worrell & P Spirakis (eds), 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018., 50, Leibniz International Proceedings in Informatics, LIPIcs, vol. 117, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, Liverpool, United Kingdom, 27/08/18. https://doi.org/10.4230/LIPIcs.MFCS.2018.50

Car-sharing between two locations: online scheduling with two servers. / Luo, Kelin; Erlebach, Thomas; Xu, Yinfeng.
43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018. ed. / Igor Potapov; James Worrell; Paul Spirakis. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. 50 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 117).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Car-sharing between two locations

T2 - 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018

AU - Luo, Kelin

AU - Erlebach, Thomas

AU - Xu, Yinfeng

PY - 2018/8/1

Y1 - 2018/8/1

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

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

KW - Car-sharing system

KW - Competitive analysis

KW - On-line scheduling

UR - https://www.scopus.com/pages/publications/85053214781

U2 - 10.4230/LIPIcs.MFCS.2018.50

DO - 10.4230/LIPIcs.MFCS.2018.50

M3 - Conference contribution

AN - SCOPUS:85053214781

SN - 9783959770866

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018

A2 - Potapov, Igor

A2 - Worrell, James

A2 - Spirakis, Paul

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

Y2 - 27 August 2018 through 31 August 2018

ER -

Luo K, Erlebach T, Xu Y. Car-sharing between two locations: online scheduling with two servers. In Potapov I, Worrell J, Spirakis P, editors, 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2018. 50. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.4230/LIPIcs.MFCS.2018.50

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

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this