On the complexity of the star p-hub center problem with parameterized triangle inequality

Li Hsuan Chen, Sun Yuan Hsieh, Ling Ju Hung, Ralf Klasing, Chia Wei Lee, Bang Ye Wu

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

5 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). ƒÀ E (w(u, x) + w(x, v)) for all vertices u, v, x ¸ V. Given a ƒ¢ƒÀ-metric graph G = (V, E,w) and a center c ¸ V, and an integer p, the ƒ¢ƒÀ-Star p-Hub Center Problem (ƒ¢ƒÀ-SpHCP) is to find a depth-2 spanning tree T of G rooted at c such that c has exactly p children and the diameter of T is minimized. The children of c in T are called hubs. For ƒÀ = 1, ƒ¢ƒÀ-SpHCP is NP-hard. (Chen et al., COCOON 2016) proved that for any ƒÃ > 0, it is NP-hard to approximate the ƒ¢ƒÀ-SpHCP to within a ratio 1.5. ƒÃ for ƒÀ = 1. In the same paper, a 5 3 -approximation algorithm was given for ƒ¢ƒÀ-SpHCP for ƒÀ = 1. In this paper, we study ƒ¢ƒÀ-SpHCP for all ƒÀ. 1 2. We show that for any ƒÃ > 0, to approximate the ƒ¢ƒÀ-SpHCP 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. ã 3 2, we have r(ƒÀ) = g(ƒÀ) = 1, i.e., ƒ¢ƒÀ-SpHCP is polynomial time solvable. If 3. ã 3 2 < ƒÀ. 2 3, we have r(ƒÀ) = g(ƒÀ) = 1+2ƒÀ.2ƒÀ2 4(1.ƒÀ). For 2 3. ƒÀ. 1, r(ƒÀ) = min{1+2ƒÀ.2ƒÀ2 4(1.ƒÀ),1 + 4ƒÀ2 5ƒÀ+1}. Moreover, for ƒÀ. 1, we have r(ƒÀ) = min{ƒÀ + 4ƒÀ2.2ƒÀ 2+ƒÀ, 2ƒÀ+1}. For ƒÀ. 2, the approximability of the problem (i.e., upper and lower bound) is linear in ƒÀ.

Original languageEnglish
Title of host publicationAlgorithms and Complexity - 10th International Conference, CIAC 2017, Proceedings
EditorsDimitris Fotakis, Aris Pagourtzis, Vangelis Th. Paschos
PublisherSpringer Verlag
Pages152-163
Number of pages12
ISBN (Print)9783319575858
DOIs
Publication statusPublished - 2017 Jan 1
Event10th International Conference on Algorithms and Complexity, CIAC 2017 - Athens, Greece
Duration: 2017 May 242017 May 26

Publication series

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

Other

Other10th International Conference on Algorithms and Complexity, CIAC 2017
CountryGreece
CityAthens
Period17-05-2417-05-26

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

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

Cite this