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

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Citations (Scopus)

Abstract

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

Original languageEnglish
Title of host publicationComputing and Combinatorics - 23rd International Conference, COCOON 2017, Proceedings
EditorsYixin Cao, Jianer Chen
PublisherSpringer Verlag
Pages112-123
Number of pages12
ISBN (Print)9783319623887
DOIs
Publication statusPublished - 2017 Jan 1
Event23rd International Conference on Computing and Combinatorics, COCOON 2017 - Hong Kong, China
Duration: 2017 Aug 32017 Aug 5

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10392 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other23rd International Conference on Computing and Combinatorics, COCOON 2017
CountryChina
CityHong Kong
Period17-08-0317-08-05

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'The approximability of the p-hub center problem with parameterized triangle inequality'. Together they form a unique fingerprint.

  • Cite this

    Chen, L. H., Hsieh, S. Y., Hung, L. J., & Klasing, R. (2017). The approximability of the p-hub center problem with parameterized triangle inequality. In Y. Cao, & J. Chen (Eds.), Computing and Combinatorics - 23rd International Conference, COCOON 2017, Proceedings (pp. 112-123). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10392 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-62389-4_10