TY - GEN
T1 - Hardness and Approximation for the Star β -Hub Routing Cost Problem in Δβ -Metric Graphs
AU - Tsai, Meng Shiou
AU - Hsieh, Sun Yuan
AU - Hung, Ling Ju
N1 - Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.
PY - 2024
Y1 - 2024
N2 - Minimizing transportation costs through the design of a hub-and-spoke network is a crucial concern in hub location problems (HLP). Within the realm of HLP, the Δβ -Star p -Hub Routing Cost Problem (Δβ -SpHRP) represents an open problem stemming from the Star p -Hub Routing Cost Problem (SpHRP) discussed in a publication by [Yeh et al., Theoretical Computer Science, 2022]. The Δβ -SpHRP deals with a specific vertex c, a positive integer p, and a Δβ -metric graph denoted as G, which is an undirected, complete, and weighted graph adhering to the β -triangle inequality. The objective is to identify a spanning tree T that satisfies the following conditions: it is rooted at c, contains exactly p hubs adjacent to c, and assigns each remaining vertex to a hub while minimizing the routing cost of T. This paper expands the input instances from metric graphs to Δβ -metric graphs. Our research demonstrates that SpHRP is NP-hard for any β>12, indicating that SpHRP remains NP-hard for various subclasses of metric graphs. For approximation algorithms, we introduce two approaches that improve upon previous results, particularly when β is close to 12.
AB - Minimizing transportation costs through the design of a hub-and-spoke network is a crucial concern in hub location problems (HLP). Within the realm of HLP, the Δβ -Star p -Hub Routing Cost Problem (Δβ -SpHRP) represents an open problem stemming from the Star p -Hub Routing Cost Problem (SpHRP) discussed in a publication by [Yeh et al., Theoretical Computer Science, 2022]. The Δβ -SpHRP deals with a specific vertex c, a positive integer p, and a Δβ -metric graph denoted as G, which is an undirected, complete, and weighted graph adhering to the β -triangle inequality. The objective is to identify a spanning tree T that satisfies the following conditions: it is rooted at c, contains exactly p hubs adjacent to c, and assigns each remaining vertex to a hub while minimizing the routing cost of T. This paper expands the input instances from metric graphs to Δβ -metric graphs. Our research demonstrates that SpHRP is NP-hard for any β>12, indicating that SpHRP remains NP-hard for various subclasses of metric graphs. For approximation algorithms, we introduce two approaches that improve upon previous results, particularly when β is close to 12.
UR - http://www.scopus.com/inward/record.url?scp=85180532510&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85180532510&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-49190-0_7
DO - 10.1007/978-3-031-49190-0_7
M3 - Conference contribution
AN - SCOPUS:85180532510
SN - 9783031491894
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 97
EP - 111
BT - Computing and Combinatorics - 29th International Conference, COCOON 2023, Proceedings
A2 - Wu, Weili
A2 - Tong, Guangmo
PB - Springer Science and Business Media Deutschland GmbH
T2 - 29th International Computing and Combinatorics Conference, COCOON 2023
Y2 - 15 December 2023 through 17 December 2023
ER -