A hard dial-a-ride problem that is easy on average

DOI10.1007/S10951-005-6811-3zbMath1123.90019OpenAlexW1990779476MaRDI QIDQ880497

Sven O. Krumke, Amin Coja-Oghlan, Till Nierhoff

Publication date: 15 May 2007

Published in: Journal of Scheduling (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10951-005-6811-3

zbMATH Keywords

approximation algorithmNP-hardaverage-case analysis

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) Discrete location and assignment (90B80)

Related Items (3)

The complexity and on-line algorithm for automated storage and retrieval system with stacker cranes on one rail ⋮ An empirical analysis of heuristics for solving the two-machine flow shop problem with job release times ⋮ An Improved Online Algorithm for the Traveling Repairperson Problem on a Line

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The Steiner problem with edge lengths 1 and 2
• Heuristics for semirandom graph problems
• Nonpreemptive Ensemble Motion Planning on a Tree
• A heuristic for the Stacker Crane Problem on trees which is almost surely exact
• Efficient Solutions to Some Transportation Problems with Applications to Minimizing Robot Arm Travel
• A Note on the Complexity of a Simple Transportation Problem
• 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

This page was built for publication: A hard dial-a-ride problem that is easy on average