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

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

8 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationComputing and Combinatorics - 22nd International Conference, COCOON 2016, Proceedings
EditorsThang N. Dinh, My T. Thai
PublisherSpringer Verlag
Pages222-234
Number of pages13
ISBN (Print)9783319426334
DOIs
Publication statusPublished - 2016
Event22nd International Conference on Computing and Combinatorics, COCOON 2016 - Ho Chi Minh City, Viet Nam
Duration: 2016 Aug 22016 Aug 4

Publication series

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

Other

Other22nd International Conference on Computing and Combinatorics, COCOON 2016
Country/TerritoryViet Nam
CityHo Chi Minh City
Period16-08-0216-08-04

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Approximation algorithms for the star k-hub center problem in metric graphs'. Together they form a unique fingerprint.

Cite this