Nothing Special   »   [go: up one dir, main page]
Document Open Access Logo

Tight Analysis of the Smartstart Algorithm for Online Dial-a-Ride on the Line

Authors Alexander Birx, Yann Disser

PDF
Thumbnail PDF

File

LIPIcs.STACS.2019.15.pdf
  • Filesize: 0.5 MB
  • 17 pages

Document Identifiers

Author Details

Alexander Birx
  • Institute of Mathematics and Graduate School CE, TU Darmstadt, Germany
Yann Disser
  • Institute of Mathematics and Graduate School CE, TU Darmstadt, Germany

Funding

This work was supported by the "Excellence Initiative" of the German Federal and State Governments and the Graduate School CE at TU Darmstadt.

Cite AsGet BibTex

Alexander Birx and Yann Disser. Tight Analysis of the Smartstart Algorithm for Online Dial-a-Ride on the Line. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 15:1-15:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.STACS.2019.15

Abstract

The online Dial-a-Ride problem is a fundamental online problem in a metric space, where transportation requests appear over time and may be served in any order by a single server with unit speed. Restricted to the real line, online Dial-a-Ride captures natural problems like controlling a personal elevator. Tight results in terms of competitive ratios are known for the general setting and for online TSP on the line (where source and target of each request coincide). In contrast, online Dial-a-Ride on the line has resisted tight analysis so far, even though it is a very natural online problem. We conduct a tight competitive analysis of the Smartstart algorithm that gave the best known results for the general, metric case. In particular, our analysis yields a new upper bound of 2.94 for open, non-preemptive online Dial-a-Ride on the line, which improves the previous bound of 3.41 [Krumke'00]. The best known lower bound remains 2.04 [SODA'17]. We also show that the known upper bound of 2 [STACS'00] regarding Smartstart’s competitive ratio for closed, non-preemptive online Dial-a-Ride is tight on the line.

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. 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
  5. 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
  6. 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
  7. 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
  8. Esteban Feuerstein and Leen Stougie. On-line Single-server Dial-a-ride Problems. Theoretical Computer Science, 268(1):91-105, 2001. Google Scholar
  9. 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
  10. D. J. Guan. Routing a Vehicle of Capacity Greater Than One. Discrete Applied Mathematics, 81(1-3):41-57, 1998. Google Scholar
  11. 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
  12. 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
  13. Sven O. Krumke. Online Optimization Competitive Analysis and Beyond, 2001. Habilitation thesis. Google Scholar
  14. 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
  15. 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
  16. Maarten Lipmann. On-Line Routing. PhD thesis, Technical University Eindhoven, 2003. 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