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

DOI10.1016/j.tcs.2022.04.007zbMath1492.68111OpenAlexW4223950885WikidataQ114129121 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 algorithmsapproximation algorithmsmetric graphsproblem complexityhub allocation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Discrete location and assignment (90B80) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

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

This page was built for publication: Hardness and approximation for the star \(p\)-hub routing cost problem in metric graphs