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

研究成果: Article同行評審

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

原文English
頁(從 - 到)92-112
頁數21
期刊Journal of Computer and System Sciences
92
DOIs
出版狀態Published - 2018 三月

All Science Journal Classification (ASJC) codes

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

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

引用此