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

摘要

AbstractA complete weighted graphG=(V,E,w)is calledΔβ-metric, for someβ≥1/2, ifGsatisfies theβ-triangle inequality,i.e.,w(u,v)≤β⋅(w(u,x)+w(x,v))for all verticesu,v,x∈V. Given aΔβ-metric graphG=(V,E,w)and a centerc∈V, and an integerp, theΔβ-Starp-Hub Center problem(Δβ-SpHCP) is to find a depth-2 spanning treeTofGrooted atcsuch thatchas exactlypchildren (also called hubs) and the diameter ofTis minimized. In this paper, we studyΔβ-SpHCP for allβ≥12. We show that for anyϵ0, to approximate theΔβ-SpHCP to a ratiog(β)−ϵis NP-hard and giver(β)-approximation algorithms for the same problem whereg(β)andr(β)are functions ofβ. A subclass of metric graphs is identified thatΔβ-SpHCP is polynomial-time solvable. Moreover, somer(β)-approximation algorithms given in this paper meet approximation lower bounds.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.•Somer(β)-approximation algorithms meet the lower bound of the approximability.•Forβ=1, the gap between the upper and lower bounds of approximability is reduced.