Approximation algorithms for the star k-hub center problem in metric graphs

DOI10.1007/978-3-319-42634-1_18MaRDI QIDQ2817864zbMATH OpenOpenAlexFDO

Authors Li-Hsuan Chen, Dun-Wei Cheng, Sun-Yuan Hsieh, Ling-Ju Hung, Chia-Wei Lee, Bang Ye Wu

Publication date 2 September 2016

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-42634-1_18

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• The hardness and approximation of the star \(p\)-hub center problem
• Hardness and approximation for the star \(p\)-hub routing cost problem in metric graphs
• Approximability and inapproximability of the star \(p\)-hub center problem with parameterized triangle inequality
• On the Complexity of the Star p-hub Center Problem with Parameterized Triangle Inequality
• Approximation algorithms for the \(p\)-hub center routing problem in parameterized metric graphs

Cites work

• scientific article; zbMATH DE number 1803765 (Why is no real title available?)
• A 2-phase algorithm for solving the single allocation p-hub center problem
• Analytical approach to parallel repetition
• Integer programming formulations of discrete hub location problems
• Introduction to algorithms.
• Network hub location problems: The state of the art
• On the single-assignment \(p\)-hub center problem
• Star p-hub center problem and star p-hub median problem with bounded path lengths
• The hardness and approximation of the star \(p\)-hub center problem
• Uncapacitated single and multiple allocation \(p\)-hub center problems

Cited in

(13)

• Algorithms for solving the \(k\)-star hub problem for trees and series-parallel graphs
• A parameterized approximation algorithm for the multiple allocation \(k\)-hub center
• On the Complexity of the Star p-hub Center Problem with Parameterized Triangle Inequality
• Improved hardness and approximation results for single allocation hub location
• On the approximability of the single allocation \(p\)-hub center problem with parameterized triangle inequality
• Approximation algorithms for median hub location problems
• Approximability and inapproximability of the star \(p\)-hub center problem with parameterized triangle inequality
• Improved hardness and approximation results for single allocation hub location problems
• Hardness and approximation for the star \(p\)-hub routing cost problem in metric graphs
• The hardness and approximation of the star \(p\)-hub center problem
• Approximation algorithms for the \(p\)-hub center routing problem in parameterized metric graphs
• Approximation Algorithm for Cycle-Star Hub Network Design Problems and Cycle-Metric Labeling Problems
• scientific article; zbMATH DE number 2089224 (Why is no real title available?)

This page was built for publication: Approximation algorithms for the star \(k\)-hub center problem in metric graphs

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