Improved bounds for open online dial-a-ride on the line

DOI10.1007/S00453-022-01061-4OpenAlexW2954136843MaRDI QIDQ2701389

Kevin Schewior, Alexander Birx, Yann Disser

Publication date: 28 April 2023

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-022-01061-4

zbMATH Keywords

competitive analysisonline algorithmscompetitive ratiodial-a-ride on the lineelevator problemsmartstart

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Related Items (1)

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

Uses Software

• DARCLASS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Routing a vehicle of capacity greater than one
• News from the online traveling repairman.
• On-line dial-a-ride problems under a restricted information model
• The Online TSP Against Fair Adversaries
• Computer-Aided Complexity Classification of Dial-a-Ride Problems
• 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
• Efficient Solutions to Some Transportation Problems with Applications to Minimizing Robot Arm Travel
• 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
• Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem
• Online Dial-A-Ride Problem with Time-Windows Under a Restricted Information Model
• Algorithmic Applications in Management
• Approximation and Online Algorithms
• Algorithms for the on-line travelling salesman
• On-line single-server dial-a-ride problems

This page was built for publication: Improved bounds for open online dial-a-ride on the line