Document Open Access Logo

Improved Bounds for Open Online Dial-a-Ride on the Line

Authors Alexander Birx, Yann Disser, Kevin Schewior

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2019.21.pdf
  • Filesize: 0.57 MB
  • 22 pages

Document Identifiers

Author Details

Alexander Birx
  • Institute of Mathematics and Graduate School CE, TU Darmstadt, Germany
Yann Disser
  • Institute of Mathematics, TU Darmstadt, Germany
Kevin Schewior
  • Institut für Informatik, Technische Universität München, Garching, Germany

Funding

  • Birx, Alexander: This work was supported by the "Excellence Initiative" of the German Federal and State Governments and the Graduate School CE at TU Darmstadt.
  • Disser, Yann: This work was supported by the "Excellence Initiative" of the German Federal and State Governments and the Graduate School CE at TU Darmstadt.
  • Schewior, Kevin: Supported by the DAAD within the PRIME program using funds of BMBF and the EU Marie Curie Actions.

Cite AsGet BibTex

Alexander Birx, Yann Disser, and Kevin Schewior. Improved Bounds for Open Online Dial-a-Ride on the Line. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 21:1-21:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.21

Abstract

We consider the open, non-preemptive online Dial-a-Ride problem on the real line, where transportation requests appear over time and need to be served by a single server. We give a lower bound of 2.0585 on the competitive ratio, which is the first bound that strictly separates online Dial-a-Ride on the line from online TSP on the line in terms of competitive analysis, and is the best currently known lower bound even for general metric spaces. On the other hand, we present an algorithm that improves the best known upper bound from 2.9377 to 2.6662. The analysis of our algorithm is tight.

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
  • Mathematics of computing → Combinatorial optimization
Keywords
  • dial-a-ride on the line
  • elevator problem
  • online algorithms
  • competitive analysis
  • smartstart
  • competitive ratio

Metrics

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

Related Versions

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), pages 639-650, 2000. Google Scholar
  2. Mikhail J. Atallah and S. Rao Kosaraju. Efficient Solutions to Some Transportation Problems with Applications to Minimizing Robot Arm Travel. SIAM Journal on Computing, 17(5), 1988. Google Scholar
  3. G. Ausiello, E. Feuerstein, S. Leonardi, L. Stougie, and M. Talamo. Algorithms for the On-Line Travelling Salesman. Algorithmica, 29(4):560-581, 2001. Google Scholar
  4. A. Birx and Y. Disser. Tight analysis of the Smartstart algorithm for online Dial-a-Ride on the line. In Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science (STACS), 2019. Full version: https://arxiv.org/abs/1901.04272. Google Scholar
  5. 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 Symposium on Discrete Algorithms (SODA), pages 994-1005, 2017. Google Scholar
  6. Michiel Blom, Sven O. Krumke, Willem E. de Paepe, and Leen Stougie. The Online TSP Against Fair Adversaries. INFORMS Journal on Computing, 13(2):138-148, 2001. Google Scholar
  7. Moses Charikar and Balaji Raghavachari. The Finite Capacity Dial-A-Ride Problem. In Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS), pages 458-467, 1998. Google Scholar
  8. Willem E. de Paepe, Jan Karel Lenstra, Jiri Sgall, René A. Sitters, and Leen Stougie. Computer-Aided Complexity Classification of Dial-a-Ride Problems. INFORMS Journal on Computing, 16(2):120-132, 2004. Google Scholar
  9. Esteban Feuerstein and Leen Stougie. On-line Single-server Dial-a-ride Problems. Theoretical Computer Science, 268(1):91-105, 2001. Google Scholar
  10. Paul C. Gilmore and Ralph E. Gomory. Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem. Operations Research, 12(5):655-679, 1964. Google Scholar
  11. D. J. Guan. Routing a Vehicle of Capacity Greater Than One. Discrete Applied Mathematics, 81(1-3):41-57, 1998. Google Scholar
  12. Dietrich Hauptmeier, Sven Oliver Krumke, and Jörg Rambau. The Online Dial-a-Ride Problem Under Reasonable Load. In Proceedings of the 4th Italian Conference on Algorithms and Complexity (CIAC), pages 125-136, 2000. Google Scholar
  13. Patrick Jaillet and Michael R. Wagner. Generalized Online Routing: New Competitive Ratios, Resource Augmentation, and Asymptotic Analyses. Operations Research, 56(3):745-757, 2008. Google Scholar
  14. Sven O. Krumke. Online Optimization Competitive Analysis and Beyond, 2001. Habilitation thesis. Google Scholar
  15. 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), pages 258-269, 2006. Google Scholar
  16. Sven O. Krumke, Luigi Laura, Maarten Lipmann, Alberto Marchetti-Spaccamela, Willem de Paepe, Diana Poensgen, and Leen Stougie. Non-abusiveness Helps: An O(1)-Competitive Algorithm for Minimizing the Maximum Flow Time in the Online Traveling Salesman Problem. In Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX), pages 200-214, 2002. Google Scholar
  17. Maarten Lipmann, Xiwen Lu, Willem E. de Paepe, Rene A. Sitters, and Leen Stougie. On-Line Dial-a-Ride Problems Under a Restricted Information Model. Algorithmica, 40(4):319-329, 2004. Google Scholar
  18. 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), pages 85-94, 2005. Google Scholar
  19. Fanglei Yi, Yinfeng Xu, and Chunlin Xin. Online Dial-a-ride Problem with Time-windows Under a Restricted Information Model. In Proceedings of the 2nd International Conference on Algorithmic Aspects in Information and Management (AAIM), pages 22-31, 2006. 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact