Approximation Algorithms for the p-Hub Center Routing Problem in Parameterized Metric Graphs.
Li-Hsuan ChenSun-Yuan HsiehLing-Ju HungRalf KlasingPublished in: IWOCA (2018)
Keyphrases
- approximation algorithms
- routing problem
- undirected graph
- np hard
- special case
- vehicle routing problem
- multicommodity flow
- vertex cover
- worst case
- vehicle routing
- minimum cost
- facility location problem
- exact algorithms
- routing algorithm
- primal dual
- approximation guarantees
- approximation ratio
- spanning tree
- shortest path
- polynomial time approximation
- travel time
- weighted graph
- constant factor
- randomized algorithms
- optimal solution
- graph structure
- directed graph
- wireless sensor networks
- disjoint paths
- lower bound