Approximability and inapproximability of the star \(p\)-hub center problem with parameterized triangle inequality
From MaRDI portal
Publication:1678171
DOI10.1016/j.jcss.2017.09.012zbMath1380.68309OpenAlexW2764084197MaRDI QIDQ1678171
Li-Hsuan Chen, Ling-Ju Hung, Bang Ye Wu, Chia-Wei Lee, Sun-Yuan Hsieh, Ralf Klasing, 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
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
On the approximability of the single allocation \(p\)-hub center problem with parameterized triangle inequality, Hardness and approximation for the star \(p\)-hub routing cost problem in metric graphs, A Modern View on Stability of Approximation, Approximation algorithms for the \(p\)-hub center routing problem in parameterized metric graphs, A combined average-case and worst-case analysis for an integrated hub location and revenue management problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Performance guarantees for the TSP with a parameterized triangle inequality
- Approximation algorithms for the TSP with sharpened triangle inequality
- On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs 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
- Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman 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
- An improved approximation algorithm for the traveling salesman problem with relaxed triangle inequality
- 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
- Handbook of Approximation Algorithms and Metaheuristics
- Improved Lower Bounds on the Approximability of the Traveling Salesman Problem
- Performance Guarantees for Approximation Algorithms Depending on Parametrized Triangle Inequalities
- Analytical approach to parallel repetition
- On the Complexity of the Star p-hub Center Problem with Parameterized Triangle Inequality
