Tight Competitive Analyses of Online Car-Sharing Problems

Authors Ya-Chun Liang, Kuan-Yun Lai, Ho-Lin Chen, Kazuo Iwama



PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2021.50.pdf
  • Filesize: 0.59 MB
  • 14 pages

Document Identifiers

Author Details

Ya-Chun Liang
  • Department of Industrial Engineering and Engineering Management, National Tsing Hua University, Hsinchu, Taiwan
Kuan-Yun Lai
  • Department of Industrial Engineering and Engineering Management, National Tsing Hua University, Hsinchu, Taiwan
Ho-Lin Chen
  • Department of Electrical Engineering, National Taiwan University, Taipei, Taiwan
Kazuo Iwama
  • Department of Industrial Engineering and Engineering Management, National Tsing Hua University, Hsinchu, Taiwan

Cite AsGet BibTex

Ya-Chun Liang, Kuan-Yun Lai, Ho-Lin Chen, and Kazuo Iwama. Tight Competitive Analyses of Online Car-Sharing Problems. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 50:1-50:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ISAAC.2021.50

Abstract

The car-sharing problem, proposed by Luo, Erlebach and Xu in 2018, mainly focuses on an online model in which there are two locations: 0 and 1, and k total cars. Each request which specifies its pick-up time and pick-up location (among 0 and 1, and the other is the drop-off location) is released in each stage a fixed amount of time before its specified start (i.e. pick-up) time. The time between the booking (i.e. released) time and the start time is enough to move empty cars between 0 and 1 for relocation if they are not used in that stage. The model, called kS2L-F, assumes that requests in each stage arrive sequentially regardless of the same booking time and the decision (accept or reject) must be made immediately. The goal is to accept as many requests as possible. In spite of only two locations, the analysis does not seem easy and the (tight) competitive ratio (CR) is only known to be 2.0 for k = 2 and 1.5 for a restricted value of k, i.e., a multiple of three. In this paper, we remove all the holes of unknown CR’s; namely we prove that the CR is 2k/(k + ⌊k/3⌋) for all k ≥ 2. Furthermore, if the algorithm can delay its decision until all requests have come in each stage, the CR is improved to roughly 4/3. We can take this advantage even further, precisely we can achieve a CR of (2+R)/3 if the number of requests in each stage is at most Rk, 1 ≤ R ≤ 2, where we do not have to know the value of R in advance. Finally we demonstrate that randomization also helps to get (slightly) better CR’s.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Car-sharing
  • Competitive analysis
  • On-line scheduling
  • Randomized algorithm

Metrics

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

References

  1. Norbert Ascheuer, Sven O. 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), pages 639-650, 2000. Google Scholar
  2. 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 2017 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’17), pages 994-1005, 2017. URL: https://doi.org/10.1137/1.9781611974782.63.
  3. Kateřina Böhmová, Yann Disser, Matúš Mihalák, and Rastislav Šrá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, 2016. Google Scholar
  4. Ananya Christman, William Forcier, and Aayam Poudel. From theory to practice: maximizing revenues for on-line dial-a-ride. Journal of Combinatorial Optimization, 35(2):512-529, 2018. Google Scholar
  5. Esteban Feuerstein and Leen Stougie. On-line single-server dial-a-ride problems. Theoretical Computer Science, 268(1):91-105, 2001. Google Scholar
  6. Sven O. Krumke, Willem E. 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 Third International Conference on Approximation and Online Algorithms (WAOA’05), pages 258-269, 2005. URL: https://doi.org/10.1007/11671411_20.
  7. Kelin Luo, Thomas Erlebach, and Yinfeng Xu. Car-sharing between two locations: Online scheduling with flexible advance bookings. In 24th International Computing and Combinatorics Conference (COCOON’18), volume 10976 of LNCS, pages 242-254, 2018. Google Scholar
  8. Kelin Luo, Thomas Erlebach, and Yinfeng Xu. Car-Sharing between Two Locations: Online Scheduling with Two Servers. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS’18), volume 117 of LIPIcs, pages 50:1-50:14, 2018. URL: https://doi.org/10.4230/LIPIcs.MFCS.2018.50.
  9. Kelin Luo, Thomas Erlebach, and Yinfeng Xu. Online Scheduling of Car-Sharing Requests Between Two Locations with Many Cars and Flexible Advance Bookings. In 29th International Symposium on Algorithms and Computation (ISAAC’18), volume 123 of LIPIcs, pages 64:1-64:13, 2018. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2018.64.
  10. 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’19), volume 126 of LIPIcs, pages 51:1-51:14, 2019. URL: https://doi.org/10.4230/LIPIcs.STACS.2019.51.
  11. Andrew Chi-Chin Yao. Probabilistic computations: Toward a unified measure of complexity. In 18th Annual Symposium on Foundations of Computer Science (FOCS’77), pages 222-227. IEEE Computer Society, 1977. Google Scholar
  12. Fanglei Yi and Lei Tian. On the online dial-a-ride problem with time-windows. In International Conference on Algorithmic Applications in Management (AAIM’05), pages 85-94. Springer, 2005. Google Scholar
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