Car-Sharing on a Star Network: On-Line Scheduling with k Servers

Authors Kelin Luo , Thomas Erlebach , Yinfeng Xu



PDF
Thumbnail PDF

File

LIPIcs.STACS.2019.51.pdf
  • Filesize: 0.54 MB
  • 14 pages

Document Identifiers

Author Details

Kelin Luo
  • School of Management, Xi'an Jiaotong University, Xi'an, China
Thomas Erlebach
  • Department of Informatics, University of Leicester, Leicester, United Kingdom
Yinfeng Xu
  • School of Management, Xi'an Jiaotong University, Xi'an, China

Cite AsGet BibTex

Kelin Luo, Thomas Erlebach, and Yinfeng Xu. Car-Sharing on a Star Network: On-Line Scheduling with k Servers. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 51:1-51:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.STACS.2019.51

Abstract

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

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
Keywords
  • Car-Sharing System
  • On-Line Scheduling
  • Competitive Analysis
  • Star Network

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Norbert Ascheuer, Sven Oliver Krumke, and Jörg Rambau. Online Dial-a-Ride Problems: Minimizing the Completion Time. In Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science (STACS '00), volume 1770 of LNCS, pages 639-650. Springer, 2000. URL: http://dx.doi.org/10.1007/3-540-46541-3_53.
  2. Baruch Awerbuch, Yair Bartal, Amos Fiat, and Adi Rosén. Competitive Non-Preemptive Call Control. In Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '94), pages 312-320. ACM/SIAM, 1994. URL: http://dl.acm.org/citation.cfm?id=314464.314510.
  3. Antje Bjelde, Yann Disser, Jan Hackfeld, Christoph Hansknecht, Maarten Lipmann, Julie Meißner, Kevin Schewior, Miriam Schlöter, and Leen Stougie. Tight Bounds for Online TSP on the Line. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '17), pages 994-1005. SIAM, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.63.
  4. Katerina Böhmová, Yann Disser, Matús Mihalák, and Rastislav Srámek. Scheduling Transfers of Resources over Time: Towards Car-Sharing with Flexible Drop-Offs. In Proceedings of the 12th Latin American Symposium on Theoretical Informatics (LATIN'16), volume 9644 of LNCS, pages 220-234. Springer, 2016. URL: http://dx.doi.org/10.1007/978-3-662-49529-2_17.
  5. Allan Borodin and Ran El-Yaniv. Online computation and competitive analysis. Cambridge University Press, 1998. Google Scholar
  6. Ananya Christman, William Forcier, and Aayam Poudel. From theory to practice: Maximizing revenues for on-line dial-a-ride. J. Comb. Optim., 35(2):512-529, 2018. URL: http://dx.doi.org/10.1007/s10878-017-0188-z.
  7. Sven Oliver Krumke, Willem de Paepe, Diana Poensgen, Maarten Lipmann, Alberto Marchetti-Spaccamela, and Leen Stougie. On Minimizing the Maximum Flow Time in the Online Dial-a-Ride Problem. In Proceedings of the 3rd International Workshop on Approximation and Online Algorithms (WAOA 2005), volume 3879 of LNCS, pages 258-269. Springer, 2006. URL: http://dx.doi.org/10.1007/11671411_20.
  8. Richard J. Lipton and Andrew Tomkins. Online Interval Scheduling. In Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '94), pages 302-311. ACM/SIAM, 1994. URL: http://dl.acm.org/citation.cfm?id=314464.314506.
  9. Kelin Luo, Thomas Erlebach, and Yinfeng Xu. Car-Sharing Between Two Locations: Online Scheduling with Flexible Advance Bookings. In Proceedings of the 24th International Conference on Computing and Combinatorics (COCOON 2018), volume 10976 of LNCS, pages 242-254. Springer, 2018. URL: http://dx.doi.org/10.1007/978-3-319-94776-1_21.
  10. Kelin Luo, Thomas Erlebach, and Yinfeng Xu. Car-Sharing between Two Locations: Online Scheduling with Two Servers. In Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), volume 117 of LIPIcs, pages 50:1-50:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.MFCS.2018.50.
  11. Kelin Luo, Thomas Erlebach, and Yinfeng Xu. Online Scheduling of Car-Sharing Requests between Two Locations with Many Cars and Flexible Advance Bookings. In Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC 2018), volume 123 of LIPIcs, pages 64:1-64:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.ISAAC.2018.64.
  12. Fanglei Yi and Lei Tian. On the Online Dial-A-Ride Problem with Time-Windows. In Proceedings of the 1st International Conference on Algorithmic Applications in Management (AAIM '05), volume 3521 of LNCS, pages 85-94. Springer, 2005. URL: http://dx.doi.org/10.1007/11496199_11.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail