Paper Info
Title
The hardness and approximation of the star p-hub center problem.
Abstract
We consider the star p-hub center problem recently introduced by Yaman and Elloumi [H. Yaman and S. Elloumi. Star p-hub center problem and star p-hub median problem with bounded path lengths, Comput. Oper. Res., 39 (11) (2012) 2725–2732]. We first show that the problem does not admit a (1.25−ϵ)-approximation algorithm for any ϵ>0 unless P=NP. In particular this gives the first strong NP-hardness result for the problem in a metric space. We also present, complementing the inapproximability result, a purely combinatorial 3.5-approximation algorithm for the star p-hub center problem.
Year
DOI
Venue
2013
10.1016/j.orl.2012.12.007
Operations Research Letters
Keywords
Field
DocType
Star p-hub center problem,NP-hardness,Approximation algorithm,Hardness of approximation
Discrete mathematics,Approximation algorithm,Mathematical optimization,Combinatorics,Hardness of approximation,Metric space,Mathematics,Bounded function
Journal
Volume
Issue
ISSN
41
2
0167-6377
Citations 
PageRank 
References 
5
0.45
9
Authors
1
Name
Order
Citations
PageRank
Hongyu Liang18416.39