An Approximation Algorithm for Star p-Hub Routing Cost Problem

Sun-Yuan Hsieh, Li Hsuan Chen, Wei Lu

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

Abstract

Given a metric graph G = (V,E,w), a center c ε V, and an integer p, we discuss the Star p-Hub Routing Cost Problem in this paper. We want obtain a depth-2 tree which has a root and root is adjacent to p vertices called hubs. We call that this tree is a star p-hub tree and let the sum of distance in tree between all pairs of vertices be minimum. We prove the Star p-Hub Routing Cost Problem is NP-hard by reducing the Exact Cover by 3-Sets Problem to it. The Exact Cover by 3-Sets Problem is a variation of set cover problem and known NP-hard problem. After proving the Star p-Hub Routing Cost Problem is NP-hard, we present a 4-approximation algorithm running in polynomial time O(n2) for the Star p-Hub Routing Cost Problem.

Original languageEnglish
Title of host publicationNew Trends in Computer Technologies and Applications - 23rd International Computer Symposium, ICS 2018, Revised Selected Papers
EditorsChuan-Yu Chang, Chien-Chou Lin, Horng-Horng Lin
PublisherSpringer Verlag
Pages524-531
Number of pages8
ISBN (Print)9789811391897
DOIs
Publication statusPublished - 2019 Jan 1
Event23rd International Computer Symposium, ICS 2018 - Yunlin, Taiwan
Duration: 2018 Dec 202018 Dec 22

Publication series

NameCommunications in Computer and Information Science
Volume1013
ISSN (Print)1865-0929

Conference

Conference23rd International Computer Symposium, ICS 2018
CountryTaiwan
CityYunlin
Period18-12-2018-12-22

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'An Approximation Algorithm for Star p-Hub Routing Cost Problem'. Together they form a unique fingerprint.

Cite this