An Approximation Algorithm for Star p-Hub Routing Cost Problem

Sun-Yuan Hsieh; Li Hsuan Chen; Wei Lu

doi:10.1007/978-981-13-9190-3_58

An Approximation Algorithm for Star p-Hub Routing Cost Problem

Sun-Yuan Hsieh, Li Hsuan Chen, Wei Lu

Department of Computer Science and Information Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference 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(n²) for the Star p-Hub Routing Cost Problem.

Original language	English
Title of host publication	New Trends in Computer Technologies and Applications - 23rd International Computer Symposium, ICS 2018, Revised Selected Papers
Editors	Chuan-Yu Chang, Chien-Chou Lin, Horng-Horng Lin
Publisher	Springer Verlag
Pages	524-531
Number of pages	8
ISBN (Print)	9789811391897
DOIs	https://doi.org/10.1007/978-981-13-9190-3_58
Publication status	Published - 2019 Jan 1
Event	23rd International Computer Symposium, ICS 2018 - Yunlin, Taiwan Duration: 2018 Dec 20 → 2018 Dec 22

Publication series

Name	Communications in Computer and Information Science
Volume	1013
ISSN (Print)	1865-0929

Conference

Conference	23rd International Computer Symposium, ICS 2018
Country/Territory	Taiwan
City	Yunlin
Period	18-12-20 → 18-12-22

All Science Journal Classification (ASJC) codes

Computer Science(all)
Mathematics(all)

Access to Document

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

Cite this

Hsieh, S-Y., Chen, L. H., & Lu, W. (2019). An Approximation Algorithm for Star p-Hub Routing Cost Problem. In C-Y. Chang, C-C. Lin, & H-H. Lin (Eds.), New Trends in Computer Technologies and Applications - 23rd International Computer Symposium, ICS 2018, Revised Selected Papers (pp. 524-531). (Communications in Computer and Information Science; Vol. 1013). Springer Verlag. https://doi.org/10.1007/978-981-13-9190-3_58

Hsieh, Sun-Yuan ; Chen, Li Hsuan ; Lu, Wei. / An Approximation Algorithm for Star p-Hub Routing Cost Problem. New Trends in Computer Technologies and Applications - 23rd International Computer Symposium, ICS 2018, Revised Selected Papers. editor / Chuan-Yu Chang ; Chien-Chou Lin ; Horng-Horng Lin. Springer Verlag, 2019. pp. 524-531 (Communications in Computer and Information Science).

@inproceedings{0bfe6a13585b4c98b3e4ee31762fa120,

title = "An Approximation Algorithm for Star p-Hub Routing Cost Problem",

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

author = "Sun-Yuan Hsieh and Chen, {Li Hsuan} and Wei Lu",

year = "2019",

month = jan,

day = "1",

doi = "10.1007/978-981-13-9190-3_58",

language = "English",

isbn = "9789811391897",

series = "Communications in Computer and Information Science",

publisher = "Springer Verlag",

pages = "524--531",

editor = "Chuan-Yu Chang and Chien-Chou Lin and Horng-Horng Lin",

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

address = "Germany",

note = "23rd International Computer Symposium, ICS 2018 ; Conference date: 20-12-2018 Through 22-12-2018",

}

Hsieh, S-Y, Chen, LH & Lu, W 2019, An Approximation Algorithm for Star p-Hub Routing Cost Problem. in C-Y Chang, C-C Lin & H-H Lin (eds), New Trends in Computer Technologies and Applications - 23rd International Computer Symposium, ICS 2018, Revised Selected Papers. Communications in Computer and Information Science, vol. 1013, Springer Verlag, pp. 524-531, 23rd International Computer Symposium, ICS 2018, Yunlin, Taiwan, 18-12-20. https://doi.org/10.1007/978-981-13-9190-3_58

An Approximation Algorithm for Star p-Hub Routing Cost Problem. / Hsieh, Sun-Yuan; Chen, Li Hsuan; Lu, Wei.
New Trends in Computer Technologies and Applications - 23rd International Computer Symposium, ICS 2018, Revised Selected Papers. ed. / Chuan-Yu Chang; Chien-Chou Lin; Horng-Horng Lin. Springer Verlag, 2019. p. 524-531 (Communications in Computer and Information Science; Vol. 1013).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 -

Hsieh S-Y, Chen LH, Lu W. An Approximation Algorithm for Star p-Hub Routing Cost Problem. In Chang C-Y, Lin C-C, Lin H-H, editors, New Trends in Computer Technologies and Applications - 23rd International Computer Symposium, ICS 2018, Revised Selected Papers. Springer Verlag. 2019. p. 524-531. (Communications in Computer and Information Science). doi: 10.1007/978-981-13-9190-3_58

An Approximation Algorithm for Star p-Hub Routing Cost Problem

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this