Tight analysis of the lazy algorithm for open online dial-a-ride

DOI10.1007/978-3-031-38906-1_4MaRDI QIDQ6138988zbMATH OpenOpenAlexFDO

Authors Júlia Baligács, Y. Disser, Farehe Soheil, David Weckbecker

Publication date 16 January 2024

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2210.13850

zbMATH Keywords

online algorithmscompetitive analysisdial-a-ride

Mathematics Subject Classification ID

Data structures (68P05) Algorithms in computer science (68Wxx)

Abstract: In the open online dial-a-ride problem, a single server has to deliver transportation requests appearing over time in some metric space, subject to minimizing the completion time. We improve on the best known upper bounds on the competitive ratio on general metric spaces and on the half-line, for both the preemptive and non-preemptive version of the problem. We achieve this by revisiting the algorithm $extscLazy$ recently suggested in [WAOA, 2022] and giving an improved and tight analysis. More precisely, we show that it has competitive ratio $2.457$ on general metric spaces and $2.366$ on the half-line. This is the first upper bound that beats known lower bounds of 2.5 for schedule-based algorithms as well as the natural $extscReplan$ algorithm.

Cites work

• scientific article; zbMATH DE number 1629830 (Why is no real title available?)
• scientific article; zbMATH DE number 1629851 (Why is no real title available?)
• scientific article; zbMATH DE number 1947058 (Why is no real title available?)
• Algorithms for the on-line quota traveling salesman problem
• Algorithms for the on-line travelling salesman
• An improved algorithm for open online dial-a-ride
• An improved online algorithm for the traveling repairperson problem on a line
• Approximation and Online Algorithms
• Competitive analysis of the online dial-a-ride problem
• Euler is standing in line dial-a-ride problems with precedence-constraints
• Generalized Online Routing: New Competitive Ratios, Resource Augmentation, and Asymptotic Analyses
• Improved bounds for open online dial-a-ride on the line
• News from the online traveling repairman.
• On-line dial-a-ride problems under a restricted information model
• On-line single-server dial-a-ride problems
• Online k-server routing problems
• Online traveling salesman problems with rejection options
• Online traveling salesman problems with service flexibility
• Online travelling salesman problem on a circle
• The online TSP against fair adversaries
• Theory and Applications of Models of Computation
• Tight Bounds for Online TSP on the Line
• Tight analysis of the Smartstart algorithm for online dial-a-ride on the line

This page was built for publication: Tight analysis of the lazy algorithm for open online dial-a-ride

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6138988)