The approximability of the p-hub center problem with parameterized triangle inequality

Li Hsuan Chen, Sun Yuan Hsieh, Ling Ju Hung, Ralf Klasing

研究成果: Conference contribution

8 引文 斯高帕斯(Scopus)

摘要

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 β.

原文English
主出版物標題Computing and Combinatorics - 23rd International Conference, COCOON 2017, Proceedings
編輯Yixin Cao, Jianer Chen
發行者Springer Verlag
頁面112-123
頁數12
ISBN(列印)9783319623887
DOIs
出版狀態Published - 2017
事件23rd International Conference on Computing and Combinatorics, COCOON 2017 - Hong Kong, China
持續時間: 2017 八月 32017 八月 5

出版系列

名字Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
10392 LNCS
ISSN(列印)0302-9743
ISSN(電子)1611-3349

Other

Other23rd International Conference on Computing and Combinatorics, COCOON 2017
國家/地區China
城市Hong Kong
期間17-08-0317-08-05

All Science Journal Classification (ASJC) codes

  • 理論電腦科學
  • 電腦科學(全部)

指紋

深入研究「The approximability of the p-hub center problem with parameterized triangle inequality」主題。共同形成了獨特的指紋。

引用此