| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 1142411 | Operations Research Letters | 2013 | 4 Pages |
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Hongyu Liang,