Improved hardness and approximation results for single allocation hub location problems

DOI10.1016/J.TCS.2021.02.003MaRDI QIDQ2661760zbMATH OpenOpenAlexFDO

Authors Xing Wang, Guang-Ting Chen, Yong Chen, Yonghao Wang, An Zhang, Guohui Lin

Publication date 8 April 2021

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2021.02.003

zbMATH Keywords

approximation algorithmhub locationinapproximabilitymetricNP-hardness

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Discrete location and assignment (90B80) Programming involving graphs or networks (90C35)

Recommendations

• Improved hardness and approximation results for single allocation hub location
• Hardness and approximation for the star \(p\)-hub routing cost problem in metric graphs
• Approximation algorithms for the \(p\)-hub center routing problem in parameterized metric graphs
• Approximation algorithms for the star k-hub center problem in metric graphs
• Approximation algorithms for median hub location problems

Cites work

• A 2-phase algorithm for solving the single allocation p-hub center problem
• A linear program for the two-hub location problem
• Approximation algorithms for the \(p\)-hub center routing problem in parameterized metric graphs
• Approximation algorithms for the single allocation problem in hub-and-spoke networks and related metric labeling problems
• General variable neighborhood search for the uncapacitated single allocation \(p\)-hub center problem
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Hub Location and the p-Hub Median Problem
• Improved hardness and approximation results for single allocation hub location
• Integer programming formulations of discrete hub location problems
• Network hub location problems: The state of the art
• On the single-assignment \(p\)-hub center problem
• Optimal design of a distributed network with a two-level hierarchical structure
• The approximability of the \(p\)-hub center problem with parameterized triangle inequality
• The single allocation problem in the interacting three-hub network
• Uncapacitated single and multiple allocation \(p\)-hub center problems

Cited in

(7)

• Solution algorithms for the capacitated single allocation hub location problem
• Improved hardness and approximation results for single allocation hub location
• Hardness and approximation for the star \(p\)-hub routing cost problem in metric graphs
• A Note on “The Latest Arrival Hub Location Problem”
• HubLocator: An exact solution method for the multiple allocation hub location problem
• Single-allocation ordered median hub location problems
• Aggregation in hub location problems

This page was built for publication: Improved hardness and approximation results for single allocation hub location problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2661760)