TY - GEN

T1 - Approximation algorithms for the p-hub center routing problem in parameterized metric graphs

AU - Chen, Li Hsuan

AU - Hsieh, Sun Yuan

AU - Hung, Ling Ju

AU - Klasing, Ralf

N1 - Funding Information:
This study has been carried out in the frame of the “Investments for the future” Programme IdEx Bordeaux-CPU (ANR-10-IDEX-03-02). Research supported by the LaBRI under the “Projets émergents” program. The main work for this article was done while Li-Hsuan Chen and Ling-Ju Hung (corresponding author) were with the National Cheng Kung University.
Publisher Copyright:
© Springer International Publishing AG, part of Springer Nature 2018.

PY - 2018

Y1 - 2018

N2 - A complete weighted graph G = (V, E,w) is called Δβ-metric, for some β ≥ 1/2, if G satisfies the β-triangle inequality, i.e., w(u, v) ≤ β · (w(u, x) + w(x, v)) for all vertices u, v, x ∈ V. Given a Δβ -metric graph G = (V, E,w), the Single Allocation at most p-Hub Center Routing problem is to find a spanning subgraph H* of G such that (i) any pair of vertices in C* is adjacent in H* where C* ⊂ V and |C*|≤p; (ii) any pair of vertices in V\C* is not adjacent in H*; (iii) each v∈V\C* is adjacent to exactly one vertex in C*; and (iv) the routing cost (Formula Presented) is minimized where (Formula Presented) and f*(u),f* (v) are the vertices in C* adjacent to u and v in H*, respectively. Note that (Formula Presented) if v∈C*. The vertices selected in C* are called hubs and the rest of vertices are called non-hubs. In this paper, we show that the Single Allocation at most p-Hub Center Routing problem is NP-hard in Δβ-metric graphs for any β>1/2. Moreover, we give 2β-approximation algorithms running in time O(n2) for any β>1/2 where n is the number of vertices in the input graph.

AB - A complete weighted graph G = (V, E,w) is called Δβ-metric, for some β ≥ 1/2, if G satisfies the β-triangle inequality, i.e., w(u, v) ≤ β · (w(u, x) + w(x, v)) for all vertices u, v, x ∈ V. Given a Δβ -metric graph G = (V, E,w), the Single Allocation at most p-Hub Center Routing problem is to find a spanning subgraph H* of G such that (i) any pair of vertices in C* is adjacent in H* where C* ⊂ V and |C*|≤p; (ii) any pair of vertices in V\C* is not adjacent in H*; (iii) each v∈V\C* is adjacent to exactly one vertex in C*; and (iv) the routing cost (Formula Presented) is minimized where (Formula Presented) and f*(u),f* (v) are the vertices in C* adjacent to u and v in H*, respectively. Note that (Formula Presented) if v∈C*. The vertices selected in C* are called hubs and the rest of vertices are called non-hubs. In this paper, we show that the Single Allocation at most p-Hub Center Routing problem is NP-hard in Δβ-metric graphs for any β>1/2. Moreover, we give 2β-approximation algorithms running in time O(n2) for any β>1/2 where n is the number of vertices in the input graph.

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

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

U2 - 10.1007/978-3-319-94667-2_10

DO - 10.1007/978-3-319-94667-2_10

M3 - Conference contribution

AN - SCOPUS:85049902076

SN - 9783319946665

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 115

EP - 127

BT - Combinatorial Algorithms - 29th International Workshop, IWOCA 2018, Proceedings

A2 - Leong, Hon Wai

A2 - Iliopoulos, Costas

A2 - Sung, Wing-Kin

PB - Springer Verlag

T2 - 29th International Workshop on Combinatorial Algorithms, IWOCA 2018

Y2 - 16 July 2018 through 19 July 2018

ER -