News from the online traveling repairman.

DOI10.1016/S0304-3975(02)00409-7zbMath1044.68069MaRDI QIDQ1401247

Leen Stougie, Willem E. de Paepe, Diana Poensgen, Sven O. Krumke

Publication date: 17 August 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

Competitive analysisLatencyDial-a-ride problemOnline AlgorithmsTraveling repairman

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (21)

Online \(k\)-server routing problems ⋮ Online pickup and delivery problem with constrained capacity to minimize latency ⋮ Efficient algorithms for ride-hitching in UAV travelling ⋮ On an Online Traveling Repairman Problem with Flowtimes: Worst-Case and Average-Case Analysis ⋮ Minimizing the maximum flow time in the online food delivery problem ⋮ Tight analysis of the lazy algorithm for open online dial-a-ride ⋮ An improved algorithm for open online dial-a-ride ⋮ Online ride-hitching in UAV travelling ⋮ Improved bounds for open online dial-a-ride on the line ⋮ Weighted online minimum latency problem with edge uncertainty ⋮ Competitive analysis of a dispatch policy for a dynamic multi-period routing problem ⋮ Online Vehicle Routing Problems: A Survey ⋮ Online-optimization of multi-elevator transport systems with reoptimization algorithms based on set-partitioning models ⋮ New lower bounds for online \(k\)-server routing problems ⋮ How to whack moles ⋮ Almost sure asymptotic optimality for online routing and machine scheduling problems ⋮ A new formulation for the traveling deliveryman problem ⋮ An Improved Online Algorithm for the Traveling Repairperson Problem on a Line ⋮ The online food delivery problem on stars ⋮ Online traveling salesman problem with time cost and non-zealous server ⋮ Polynomial Time Approximation Schemes for the Traveling Repairman and Other Minimum Latency Problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The minimum latency problem
• Approximation schemes for minimum latency problems
• A guessing game and randomized online algorithms
• The complexity of the travelling repairman problem
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• Algorithms for the on-line travelling salesman
• On-line single-server dial-a-ride problems

This page was built for publication: News from the online traveling repairman.