TY - GEN
T1 - The approximability of the p-hub center problem with parameterized triangle inequality
AU - Chen, Li Hsuan
AU - Hsieh, Sun Yuan
AU - Hung, Ling Ju
AU - Klasing, Ralf
N1 - Publisher Copyright:
© 2017, Springer International Publishing AG.
PY - 2017
Y1 - 2017
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 an integer p, the Δβ -pHub Center Problem (Δβ -pHCP) is to find a spanning subgraph H∗ of G such that (i) vertices (hubs) in C∗ ⊂V form a clique of size p in H∗ ; (ii) vertices (non-hubs) in V \C∗ form an independent set in H∗ ; (iii) each non-hub v ∈ V \C∗ is adjacent to exactly one hub in C∗ ; and (iv) the diameter D(H∗ ) is minimized. For β = 1, Δβ -pHCP is NP-hard. (Chen et al., CMCT 2016) proved that for any ε > 0, it is NP-hard to approximate the Δβ -pHCP to within a ratio43 − ε for β = 1. In the same paper, a53 -approximation algorithm was given for Δβ-pHCP for β = 1. In this paper, we study Δβ -pHCP for all β ≥12. We show that for any ε > 0, to approximate the Δβ -pHCP to a ratio g(β) − ε is NP-hard and we give r(β)-approximation algorithms for the same problem where g(β) and r(β) are functions of β. If β ≤3−√23, we have r(β) = g(β) = 1, i.e., Δβ -pHCP is polynomial time solvable. If3−√23 < β ≤23, we have r(β) = g(β) =3β−2β23(1−β). For23 ≤ β ≤5+√105, r(β) = g(β) = β + β2. Moreover, for β ≥ 1, we have g(β) = β ·4β−13β−1 and r(β) = 2β, the approximability of the problem (i.e., upper and lower bound) is linear in β.
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 an integer p, the Δβ -pHub Center Problem (Δβ -pHCP) is to find a spanning subgraph H∗ of G such that (i) vertices (hubs) in C∗ ⊂V form a clique of size p in H∗ ; (ii) vertices (non-hubs) in V \C∗ form an independent set in H∗ ; (iii) each non-hub v ∈ V \C∗ is adjacent to exactly one hub in C∗ ; and (iv) the diameter D(H∗ ) is minimized. For β = 1, Δβ -pHCP is NP-hard. (Chen et al., CMCT 2016) proved that for any ε > 0, it is NP-hard to approximate the Δβ -pHCP to within a ratio43 − ε for β = 1. In the same paper, a53 -approximation algorithm was given for Δβ-pHCP for β = 1. In this paper, we study Δβ -pHCP for all β ≥12. We show that for any ε > 0, to approximate the Δβ -pHCP to a ratio g(β) − ε is NP-hard and we give r(β)-approximation algorithms for the same problem where g(β) and r(β) are functions of β. If β ≤3−√23, we have r(β) = g(β) = 1, i.e., Δβ -pHCP is polynomial time solvable. If3−√23 < β ≤23, we have r(β) = g(β) =3β−2β23(1−β). For23 ≤ β ≤5+√105, r(β) = g(β) = β + β2. Moreover, for β ≥ 1, we have g(β) = β ·4β−13β−1 and r(β) = 2β, the approximability of the problem (i.e., upper and lower bound) is linear in β.
UR - http://www.scopus.com/inward/record.url?scp=85028457719&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85028457719&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-62389-4_10
DO - 10.1007/978-3-319-62389-4_10
M3 - Conference contribution
AN - SCOPUS:85028457719
SN - 9783319623887
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 112
EP - 123
BT - Computing and Combinatorics - 23rd International Conference, COCOON 2017, Proceedings
A2 - Cao, Yixin
A2 - Chen, Jianer
PB - Springer Verlag
T2 - 23rd International Conference on Computing and Combinatorics, COCOON 2017
Y2 - 3 August 2017 through 5 August 2017
ER -