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

DOI10.1007/978-3-319-57586-5_14zbMath1380.68310OpenAlexW2606457256MaRDI QIDQ5283364

Ralf Klasing, Sun-Yuan Hsieh, Chia-Wei Lee, Li-Hsuan Chen, Ling-Ju Hung, 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

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

Related Items

Approximability and inapproximability 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

• Performance guarantees for the TSP with a parameterized triangle inequality
• Approximation algorithms for the TSP with sharpened triangle inequality
• A 2-phase algorithm for solving the single allocation \(p\)-hub center problem
• On \(k\)-connectivity problems with sharpened triangle inequality
• Uncapacitated single and multiple allocation \(p\)-hub center problems
• Clustering to minimize the maximum intercluster distance
• Integer programming formulations of discrete hub location problems
• On the single-assignment \(p\)-hub center problem
• A general variable neighborhood search for solving the uncapacitated \(r\)-allocation \(p\)-hub Median 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
• Network hub location problems: The state of the art
• On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality
• Approximation Algorithms for the Star k-Hub Center Problem in Metric Graphs
• Improved Lower Bounds on the Approximability of the Traveling Salesman Problem
• Performance Guarantees for Approximation Algorithms Depending on Parametrized Triangle Inequalities
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item