Approximation algorithms for the star k-hub center problem in metric graphs

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

研究成果: Conference contribution

8 引文 斯高帕斯(Scopus)

摘要

Given a metric graph G = (V, E, w) and a center c ∈ V, and an integer k, the Star k-Hub Center Problem is to find a depth-2 spanning tree T of G rooted by c such that c has exactly k children and the diameter of T is minimized. Those children of c in T are called hubs. The Star k-Hub Center Problem is NP-hard. (Liang, Operations Research Letters, 2013) proved that for any ε > 0, it is NP-hard to approximate the Star k-Hub Center Problem to within a ratio 1.25 −ε. In the same paper, a 3.5-approximation algorithm was given for the Star k-Hub Center Problem. In this paper, we show that for any ε > 0, to approximate the Star k-Hub Center Problem to a ratio 1.5 − ε is NP-hard. Moreover, we give 2-approximation and 5/3-approximation algorithms for the same problem.

原文English
主出版物標題Computing and Combinatorics - 22nd International Conference, COCOON 2016, Proceedings
編輯Thang N. Dinh, My T. Thai
發行者Springer Verlag
頁面222-234
頁數13
ISBN(列印)9783319426334
DOIs
出版狀態Published - 2016
事件22nd International Conference on Computing and Combinatorics, COCOON 2016 - Ho Chi Minh City, Viet Nam
持續時間: 2016 八月 22016 八月 4

出版系列

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

Other

Other22nd International Conference on Computing and Combinatorics, COCOON 2016
國家/地區Viet Nam
城市Ho Chi Minh City
期間16-08-0216-08-04

All Science Journal Classification (ASJC) codes

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

指紋

深入研究「Approximation algorithms for the star k-hub center problem in metric graphs」主題。共同形成了獨特的指紋。

引用此