TY - GEN

T1 - An Approximation Algorithm for Star p-Hub Routing Cost Problem

AU - Hsieh, Sun-Yuan

AU - Chen, Li Hsuan

AU - Lu, Wei

PY - 2019/1/1

Y1 - 2019/1/1

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

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

UR - http://www.scopus.com/inward/record.url?scp=85069678421&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85069678421&partnerID=8YFLogxK

U2 - 10.1007/978-981-13-9190-3_58

DO - 10.1007/978-981-13-9190-3_58

M3 - Conference contribution

AN - SCOPUS:85069678421

SN - 9789811391897

T3 - Communications in Computer and Information Science

SP - 524

EP - 531

BT - New Trends in Computer Technologies and Applications - 23rd International Computer Symposium, ICS 2018, Revised Selected Papers

A2 - Chang, Chuan-Yu

A2 - Lin, Chien-Chou

A2 - Lin, Horng-Horng

PB - Springer Verlag

T2 - 23rd International Computer Symposium, ICS 2018

Y2 - 20 December 2018 through 22 December 2018

ER -