Approximability and inapproximability of the star \(p\)-hub center problem with parameterized triangle inequality
type: Item
instance of: scholarly article
title: Approximability and inapproximability of the star \(p\)-hub center problem with parameterized triangle inequality
zbMATH Open document ID: 1380.68309
author: Li-Hsuan Chen
author: Dun-Wei Cheng
author: Sun-Yuan Hsieh
author: Ling-Ju Hung
author: Ralf Klasing
author: Chia-Wei Lee
author: Bang Ye Wu
published in: Journal of Computer and System Sciences
publication date: 2017-11-14T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 6806907
zbMATH Keywords: hub allocation
zbMATH Keywords: stability of approximation
zbMATH Keywords: \(\beta\)-triangle inequality
zbMATH Keywords: metric graphs
MaRDI profile type: Publication
full work available at URL: j.jcss.2017.09.012
OpenAlex ID: W2764084197
cites work: Network hub location problems: The state of the art
cites work: On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality
cites work: Performance Guarantees for Approximation Algorithms Depending on Parametrized Triangle Inequalities
cites work: Performance guarantees for the TSP with a parameterized triangle inequality
cites work: On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality
cites work: Q4437508
cites work: On \(k\)-connectivity problems with sharpened triangle inequality
cites work: Approximation algorithms for the TSP with sharpened triangle inequality
cites work: Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem.
cites work: Q4501548
cites work: Handbook of Approximation Algorithms and Metaheuristics
cites work: Improved Lower Bounds on the Approximability of the Traveling Salesman Problem
cites work: Integer programming formulations of discrete hub location problems
cites work: Q3147668
cites work: Approximation Algorithms for the Star k-Hub Center Problem in Metric Graphs
cites work: On the Complexity of the Star p-hub Center Problem with Parameterized Triangle Inequality
cites work: Analytical approach to parallel repetition
cites work: Uncapacitated single and multiple allocation \(p\)-hub center problems
cites work: Q4198056
cites work: Clustering to minimize the maximum intercluster distance
cites work: Q3002852
cites work: Q4941164
cites work: On the single-assignment \(p\)-hub center problem
cites work: The hardness and approximation of the star \(p\)-hub center problem
cites work: A 2-phase algorithm for solving the single allocation \(p\)-hub center problem
cites work: An improved approximation algorithm for the traveling salesman problem with relaxed triangle inequality
cites work: A general variable neighborhood search for solving the uncapacitated \(r\)-allocation \(p\)-hub Median problem
cites work: Star \(p\)-hub center problem and star \(p\)-hub median problem with bounded path lengths
DOI: 10.1016/J.JCSS.2017.09.012
Recommended article: On the Complexity of the Star p-hub Center Problem with Parameterized Triangle Inequality
Recommended article: The approximability of the \(p\)-hub center problem with parameterized triangle inequality
Recommended article: The hardness and approximation of the star \(p\)-hub center problem
Recommended article: On the approximability of the single allocation \(p\)-hub center problem with parameterized triangle inequality
Recommended article: Approximation Algorithms for the Star k-Hub Center Problem in Metric Graphs
Recommended article: Star \(p\)-hub center problem and star \(p\)-hub median problem with bounded path lengths
Recommended article: Q4242386
Recommended article: Approximation algorithms for the \(p\)-hub center routing problem in parameterized metric graphs
Recommended article: Q3295505
Recommended article: Generalized \(p\)-center problems: Complexity results and approximation algorithms
description: scientific article; zbMATH DE number 6806907