Hardness and approximation for the star \(p\)-hub routing cost problem in metric graphs

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

zbMATH Keywords

analysis of algorithms; approximation algorithms; metric graphs; problem complexity; hub allocation

Mathematics Subject Classification ID

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