University of Leicester
Browse
LIPIcs-MFCS-2018-50.pdf (473.1 kB)

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

Download (473.1 kB)
conference contribution
posted on 2018-07-30, 10:56 authored by Kelin Luo, Thomas Erlebach, Yinfeng Xu
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.

History

Citation

Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, 2018, pp. 50:1-50:14 (14)

Author affiliation

/Organisation/COLLEGE OF SCIENCE AND ENGINEERING/Department of Informatics

Source

43rd International Symposium on Mathematical Foundations of Computer Science. MFCS 2018, Liverpool

Version

  • VoR (Version of Record)

Published in

Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science

Publisher

Schloss Dagstuhl - Leibniz-Zentrum für Informatik

eissn

1868-8969

Acceptance date

2018-06-13

Copyright date

2018

Available date

2018-09-07

Publisher version

http://drops.dagstuhl.de/opus/volltexte/2018/9632/

Temporal coverage: start date

2018-08-27

Temporal coverage: end date

2018-08-31

Language

en

Usage metrics

    University of Leicester Publications

    Categories

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC