On the approximability of the single allocation \(p\)-hub center problem with parameterized triangle inequality
DOI10.1007/s00453-022-00941-zzbMath1492.68103OpenAlexW4214508416MaRDI QIDQ2149101
Li-Hsuan Chen, Ling-Ju Hung, Sun-Yuan Hsieh, Ralf Klasing
Publication date: 28 June 2022
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-022-00941-z
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Discrete location and assignment (90B80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Signed and weighted graphs (05C22)
Related Items (1)
Cites Work
- Performance guarantees for the TSP with a parameterized triangle inequality
- Approximation algorithms for the TSP with sharpened triangle inequality
- General variable neighborhood search for the uncapacitated single allocation \(p\)-hub center problem
- 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
- 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.
- Optimizing fuzzy \( p\)-hub center problem with generalized value-at-risk criterion
- A general variable neighborhood search for solving the uncapacitated \(r\)-allocation \(p\)-hub Median problem
- Approximability and inapproximability of the star \(p\)-hub center problem with 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
- 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
- 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
- A Modern View on Stability of Approximation
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: On the approximability of the single allocation \(p\)-hub center problem with parameterized triangle inequality
