Hardness and approximation for the star \(p\)-hub routing cost problem in metric graphs
From MaRDI portal
Publication:2672567
DOI10.1016/j.tcs.2022.04.007zbMath1492.68111WikidataQ114129121 ScholiaQ114129121MaRDI QIDQ2672567
Hao-Ping Yeh, Wei Lu, Ralf Klasing, Ling-Ju Hung, Li-Hsuan Chen, Sun-Yuan Hsieh
Publication date: 13 June 2022
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2022.04.007
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
90C27: Combinatorial optimization
90B80: Discrete location and assignment
05C12: Distance in graphs
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25: Approximation algorithms
Cites Work
- Unnamed Item
- The capacitated \(p\)-hub median problem with integral constraints: an application to a Chinese air cargo network
- The uncapacitated hub location problem in networks under decentralized management
- Approximation algorithms for the single allocation problem in hub-and-spoke networks and related metric labeling problems
- A quadratic integer program for the location of interacting hub facilities
- Approximability and inapproximability of the star \(p\)-hub center problem with parameterized triangle inequality
- Star \(p\)-hub center problem and star \(p\)-hub median problem with bounded path lengths
- Design of intermodal logistics networks with hub delays
- The hardness and approximation of the star \(p\)-hub center problem
- Perspectives on modeling hub location problems
- On the approximability of the single allocation \(p\)-hub center problem with parameterized triangle inequality
- Approximation algorithms for the \(p\)-hub center routing problem in parameterized metric graphs
- On the minimum routing cost clustered tree problem
- Star \(p\)-hub median problem with modular arc capacities
- A PTAS for the metric case of the optimum weighted source-destination communication spanning tree problem
- Improved hardness and approximation results for single allocation hub location problems
- Approximation Algorithms for the Star k-Hub Center Problem in Metric Graphs
- Optimum Communication Spanning Trees
- The complexity of the network design problem
- A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees