Approximability and inapproximability of the star \(p\)-hub center problem with parameterized triangle inequality

DOI10.1016/j.jcss.2017.09.012zbMath1380.68309MaRDI QIDQ1678171

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

Publication date: 14 November 2017

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2017.09.012

zbMATH Keywords

metric graphs; stability of approximation; \(\beta\)-triangle inequality; hub allocation

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W25: Approximation algorithms