Approximation results for a min-max location-routing problem

DOI10.1016/j.dam.2011.09.014zbMath1238.90021OpenAlexW2008850276MaRDI QIDQ765374

Wenbin Zhu, Zhou Xu, Dongsheng Xu

Publication date: 19 March 2012

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

Full work available at URL: https://doi.org/10.1016/j.dam.2011.09.014

zbMATH Keywords

approximation algorithmapproximation hardnessmin-max location-routing

Mathematics Subject Classification ID

Transportation, logistics and supply chain management (90B06) Approximation methods and heuristics in mathematical programming (90C59) Discrete location and assignment (90B80) Approximation algorithms (68W25)

Related Items (max. 100)

A survey of recent research on location-routing problems ⋮ An overview of graph covering and partitioning ⋮ Distance constrained vehicle routing problem to minimize the total cost: algorithms and complexity ⋮ Improved approximation algorithms for some min-max and minimum cycle cover problems ⋮ Improved Approximation Algorithms for Min-Max and Minimum Vehicle Routing Problems ⋮ Better approximability results for min-max tree/cycle/path cover problems ⋮ Scheduling on a graph with release times ⋮ New approximation algorithms for the minimum cycle cover problem ⋮ New LP relaxations for minimum cycle/path/tree cover problems ⋮ New approximation algorithms for the rooted budgeted cycle cover problem ⋮ New approximation algorithms for the rooted budgeted cycle cover problem ⋮ A taxonomical analysis, current methods and objectives on location-routing problems

Cites Work

• Unnamed Item
• Unnamed Item
• Min-max tree covers of graphs.
• Location-routing: issues, models and methods
• Approximation hardness of min-max tree covers
• Combined location-routing problems: A synthesis and future research directions
• \((p-1)/(p+1)\)-approximate algorithms for \(p\)-traveling salesmen problems on a tree with minmax objective
• 2-approximation algorithms for the multi-vehicle scheduling problem on a path with release and handling times.
• A faster 2-approximation algorithm for the minmax \(p\)-traveling salesmen problem on a tree
• Minmax \(p\)-traveling salesmen location problems on a tree
• A heuristic with worst-case analysis for minimax routing of two travelling salesmen on a tree
• Approximating the minmax rooted-tree cover in a tree
• Approximation results for min-max path cover problems in vehicle routing
• Approximations for minimum and min-max vehicle routing problems
• Combinatorial optimization. Theory and algorithms.

This page was built for publication: Approximation results for a min-max location-routing problem