TY - JOUR

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

AU - Chen, Li Hsuan

AU - Cheng, Dun Wei

AU - Hsieh, Sun Yuan

AU - Hung, Ling Ju

AU - Klasing, Ralf

AU - Lee, Chia Wei

AU - Wu, Bang Ye

N1 - Funding Information:
Parts of this work were supported by the Ministry of Science and Technology of Taiwan under grants MOST 105-2221-006-164-MY3 , MOST 106-2221-E-006-037-MY3 , and MOST 103-2218-E-006-019-MY3 . Part of this work was done while Ralf Klasing was visiting the Department of Computer Science and Information Engineering at National Cheng Kung University. This study has been carried out in the frame of the “Investments for the future” Programme IdEx Bordeaux – CPU ( ANR-10-IDEX-03-02 ). Research supported by the LaBRI under the “Projets émergents” program.
Publisher Copyright:
© 2017 Elsevier Inc.

PY - 2018/3

Y1 - 2018/3

N2 - A complete weighted graph G=(V,E,w) is called Δβ-metric, for some β≥1/2, if G satisfies the β-triangle inequality, i.e., w(u,v)≤β⋅(w(u,x)+w(x,v)) for all vertices u,v,x∈V. Given a Δβ-metric graph G=(V,E,w) and a center c∈V, and an integer p, the Δβ-STAR p-HUB CENTER PROBLEM (Δβ-SpHCP) is to find a depth-2 spanning tree T of G rooted at c such that c has exactly p children (also called hubs) and the diameter of T is minimized. In this paper, we study Δβ-SpHCP for all [Formula presented]. We show that for any ϵ>0, to approximate the Δβ-SpHCP to a ratio g(β)−ϵ is NP-hard and give r(β)-approximation algorithms for the same problem where g(β) and r(β) are functions of β. A subclass of metric graphs is identified that Δβ-SpHCP is polynomial-time solvable. Moreover, some r(β)-approximation algorithms given in this paper meet approximation lower bounds.

AB - A complete weighted graph G=(V,E,w) is called Δβ-metric, for some β≥1/2, if G satisfies the β-triangle inequality, i.e., w(u,v)≤β⋅(w(u,x)+w(x,v)) for all vertices u,v,x∈V. Given a Δβ-metric graph G=(V,E,w) and a center c∈V, and an integer p, the Δβ-STAR p-HUB CENTER PROBLEM (Δβ-SpHCP) is to find a depth-2 spanning tree T of G rooted at c such that c has exactly p children (also called hubs) and the diameter of T is minimized. In this paper, we study Δβ-SpHCP for all [Formula presented]. We show that for any ϵ>0, to approximate the Δβ-SpHCP to a ratio g(β)−ϵ is NP-hard and give r(β)-approximation algorithms for the same problem where g(β) and r(β) are functions of β. A subclass of metric graphs is identified that Δβ-SpHCP is polynomial-time solvable. Moreover, some r(β)-approximation algorithms given in this paper meet approximation lower bounds.

UR - http://www.scopus.com/inward/record.url?scp=85033492275&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85033492275&partnerID=8YFLogxK

U2 - 10.1016/j.jcss.2017.09.012

DO - 10.1016/j.jcss.2017.09.012

M3 - Article

AN - SCOPUS:85033492275

VL - 92

SP - 92

EP - 112

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

SN - 0022-0000

ER -