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 - Funding Information:
Parts of this research were supported by the Ministry of Science and Technology of Taiwan under grants MOST 105–2221–E–006–164–MY3, and MOST 103–2221–E– 006–135–MY3. Li-Hsuan Chen is supported by the Ministry of Science and Technology of Taiwan under grant MOST 106–2811–E–006–008. Ling-Ju Hung is supported by the Ministry of Science and Technology of Taiwan under grants MOST 105–2811–E–006–046. 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, 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 -