Approximability and inapproximability of the star p-hub center problem with parameterized triangle inequality

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

Research output: Contribution to journalArticlepeer-review

7 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 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 (also called hubs) and the diameter of T is minimized. In this paper, we study Δ β -SpHCP for all [Formula presented]. We show that for any ϵ>0, to approximate the Δ β -SpHCP to a ratio g(β)−ϵ is NP-hard and give r(β)-approximation algorithms for the same problem where g(β) and r(β) are functions of β. A subclass of metric graphs is identified that Δ β -SpHCP is polynomial-time solvable. Moreover, some r(β)-approximation algorithms given in this paper meet approximation lower bounds.

Original languageEnglish
Pages (from-to)92-112
Number of pages21
JournalJournal of Computer and System Sciences
Volume92
DOIs
Publication statusPublished - 2018 Mar 1

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics

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

Cite this