On the Complexity of the Star p-hub Center Problem with Parameterized Triangle Inequality

DOI10.1007/978-3-319-57586-5_14MaRDI QIDQ5283364zbMATH OpenOpenAlexFDO

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

Publication date 21 July 2017

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-57586-5_14

Mathematics Subject Classification ID

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

Recommendations

• Approximability and inapproximability of the star p-hub center problem with parameterized triangle inequality
• The approximability of the \(p\)-hub center problem with parameterized triangle inequality
• The hardness and approximation of the star \(p\)-hub center problem
• On the approximability of the single allocation \(p\)-hub center problem with parameterized triangle inequality
• Approximation algorithms for the star k-hub center problem in metric graphs
• Star p-hub center problem and star p-hub median problem with bounded path lengths
• scientific article; zbMATH DE number 1285629
• Un nuevo resultado sobre la complejidad del problema delP-centro
• The parameterized complexity of the shared center problem
• The parameterized complexity of the shared center problem

Cites work

• A 2-phase algorithm for solving the single allocation p-hub center problem
• A general variable neighborhood search for solving the uncapacitated \(r\)-allocation \(p\)-hub Median problem
• Approximation algorithms for NP-hard problems.
• Approximation algorithms for the star k-hub center problem in metric graphs
• Approximation algorithms for the TSP with sharpened triangle inequality
• Clustering to minimize the maximum intercluster distance
• scientific article; zbMATH DE number 1803765 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 1954373 (Why is no real title available?)
• scientific article; zbMATH DE number 2011856 (Why is no real title available?)
• scientific article; zbMATH DE number 1489999 (Why is no real title available?)
• scientific article; zbMATH DE number 1500530 (Why is no real title available?)
• scientific article; zbMATH DE number 1507218 (Why is no real title available?)
• Improved Lower Bounds on the Approximability of the Traveling Salesman Problem
• Integer programming formulations of discrete hub location problems
• Network hub location problems: The state of the art
• On k-connectivity problems with sharpened triangle inequality
• On the single-assignment \(p\)-hub center problem
• On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality
• Performance Guarantees for Approximation Algorithms Depending on Parametrized Triangle Inequalities
• Performance guarantees for the TSP with a parameterized triangle inequality
• 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

(7)

• Approximability and inapproximability of the star p-hub center problem with parameterized triangle inequality
• The hardness and approximation of the star \(p\)-hub center problem
• 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
• The approximability of the \(p\)-hub center problem with parameterized triangle inequality
• Hardness and approximation for the star \(p\)-hub routing cost problem in metric graphs
• Approximation algorithms for the star k-hub center problem in metric graphs

This page was built for publication: On the Complexity of the Star p-hub Center Problem with Parameterized Triangle Inequality

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