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

Fingerprint

Approximation algorithms
Stars
Approximation Algorithms
Star
Routing
Costs
Computational complexity
NP-complete problem
Roots
Cover
Metric Graphs
Set Cover
NP-hard Problems
Polynomials
Polynomial time
Adjacent
Integer

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

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 = "1",
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",

}

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 proceedingConference 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

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). https://doi.org/10.1007/978-981-13-9190-3_58