Approximability and inapproximability of the star p-hub center problem with parameterized triangle inequality

作者：

Highlights：

• The lower bound and upper bound of the approximability of Δβ-SpHCP are given.

• Δβ-SpHCP is polynomial-time solvable in a subclass of metric graphs.

• Some r(β)-approximation algorithms meet the lower bound of the approximability.

• For β=1, the gap between the upper and lower bounds of approximability is reduced.

摘要

•The lower bound and upper bound of the approximability of Δβ-SpHCP are given.•Δβ-SpHCP is polynomial-time solvable in a subclass of metric graphs.•Some r(β)-approximation algorithms meet the lower bound of the approximability.•For β=1, the gap between the upper and lower bounds of approximability is reduced.

论文关键词：Hub allocation,Stability of approximation,β-triangle inequality,Metric graphs

论文评审过程：Received 2 March 2017, Revised 15 June 2017, Accepted 24 September 2017, Available online 14 October 2017, Version of Record 13 November 2017.

论文官网地址：https://doi.org/10.1016/j.jcss.2017.09.012