2-approximation algorithms for the multi-vehicle scheduling problem on a path with release and handling times.

DOI10.1016/S0166-218X(02)00596-6zbMath1034.68122MaRDI QIDQ1406038

Hiroshi Nagamochi, Yoshiyuki Karuno

Publication date: 9 September 2003

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

performance guarantee

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Related Items

An approximability result of the multi-vehicle scheduling problem on a path with release and handling times, Linear time approximation schemes for vehicle scheduling problems, Approximating the minmax rooted-tree cover in a tree, Better approximability results for min-max tree/cycle/path cover problems, Routing open shop and flow shop scheduling problems, Scheduling on a graph with release times, Approximation algorithms for single vehicle scheduling problems with release and service times on a tree or cycle, Dynamic Traveling Repair Problem with an Arbitrary Time Window, Data mule scheduling on a path with handling time and time span constraints, Minmax subtree cover problem on cacti, New LP relaxations for minimum cycle/path/tree cover problems, Single-vehicle scheduling problems with release and service times on a line, Improved algorithms for single vehicle scheduling on tree/cycle networks, Vehicle routing problems on a line-shaped network with release time constraints, Minmax Tree Cover in the Euclidean Space, Approximation results for a min-max location-routing problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Single-vehicle scheduling with time window constraints
• Vehicle scheduling on a tree with release and handling times
• \((p-1)/(p+1)\)-approximate algorithms for \(p\)-traveling salesmen problems on a tree with minmax objective
• A heuristic with worst-case analysis for minimax routing of two travelling salesmen on a tree
• Better approximation ratios for the single-vehicle scheduling problems on line-shaped networks
• Routing and Scheduling on a Shoreline with Release Times
• Special cases of traveling salesman and repairman problems with time windows
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Technical Note—Routing and Location-Routing p-Delivery Men Problems on a Path
• VEHICLE SCHEDULING ON A TREE TO MINIMIZE MAXIMUM LATENESS
• Complexity Of The Single Vehicle Scheduling Problem On Graphs
• Sales‐delivery man problems on treelike networks
• A new approximation algorithm for the capacitated vehicle routing problem on a tree