Journal article
The hardness and approximation of the star p-hub center problem
Operations research letters, v 41(2), pp 138-141
Mar 2013
Featured in Collection : UN Sustainable Development Goals @ Drexel
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.
Metrics
Details
- Title
- The hardness and approximation of the star p-hub center problem
- Creators
- Hongyu Liang - Tsinghua University
- Publication Details
- Operations research letters, v 41(2), pp 138-141
- Publisher
- Elsevier
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- School of Biomedical Engineering, Science, and Health Systems
- Web of Science ID
- WOS:000316836100004
- Scopus ID
- 2-s2.0-84872154511
- Other Identifier
- 991019320405104721
UN Sustainable Development Goals (SDGs)
This publication has contributed to the advancement of the following goals:
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Web of Science research areas
- Operations Research & Management Science