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

DOI10.1007/978-3-031-38906-1_4arXiv2210.13850OpenAlexW4385317077MaRDI QIDQ6138988

David Weckbecker, Yann Disser, Júlia Baligács, Farehe Soheil

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

competitive analysisonline algorithmsdial-a-ride

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithms for the on-line quota traveling salesman problem
• Online \(k\)-server routing problems
• News from the online traveling repairman.
• On-line dial-a-ride problems under a restricted information model
• Online travelling salesman problem on a circle
• Improved bounds for open online dial-a-ride on the line
• The Online TSP Against Fair Adversaries
• Online traveling salesman problems with service flexibility
• Tight Analysis of the Smartstart Algorithm for Online Dial-a-Ride on the Line
• Generalized Online Routing: New Competitive Ratios, Resource Augmentation, and Asymptotic Analyses
• Online traveling salesman problems with rejection options
• Tight Bounds for Online TSP on the Line
• Competitive analysis of the online dial-a-ride problem
• An Improved Online Algorithm for the Traveling Repairperson Problem on a Line
• Approximation and Online Algorithms
• Theory and Applications of Models of Computation
• Algorithms for the on-line travelling salesman
• Euler is standing in line dial-a-ride problems with precedence-constraints
• On-line single-server dial-a-ride problems
• An improved algorithm for open online dial-a-ride

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