TY - JOUR

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:
Parts of this work were supported by the Ministry of Science and Technology of Taiwan under grants MOST 105?2221?006?164?MY3, MOST 103?2218?E?006?019?MY3, and MOST 103-2221-E-006-135-MY3. This study has been carried out in the frame of the ?Investments for the future? Programme IdEx Bordeaux - SysNum (ANR-10-IDEX-03-02). Research supported by the LaBRI under the ?Projets ?mergents? program.L.-H. Chen and L.-J. Hung were supported by the Ministry of Science and Technology of Taiwan under grants MOST 106?2811?E?006?008 and MOST 105?2811?E?006?046, respectively.
Publisher Copyright:
© 2019 Elsevier B.V.

PY - 2020/2/2

Y1 - 2020/2/2

N2 - Let G=(V,E,w) be a Δβ-metric graph with a distance function w(⋅,⋅) on V such that w(v,v)=0, w(u,v)=w(v,u), and w(u,v)≤β⋅(w(u,x)+w(x,v)) for all u,v,x∈V. Given a positive integer p, let H be a spanning subgraph of G satisfying the conditions that vertices (hubs) in C⊂V form a clique of size at most p in H, vertices (non-hubs) in V∖C form an independent set in H, and each non-hub v∈V∖C is adjacent to exactly one hub in C. Define dH(u,v)=w(u,f(u))+w(f(u),f(v))+w(v,f(v)) where f(u) and f(v) are hubs adjacent to u and v in H respectively. Notice that if u is a hub in H then w(u,f(u))=0. Let r(H)=∑u,v∈VdH(u,v) be the routing cost of H. The SINGLE ALLOCATION AT MOST p-HUB CENTER ROUTING problem is to find a spanning subgraph H of G such that r(H) is minimized. 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. Finally, we show that the approximation ratio of our algorithms is at least Ω(β), and we examine the structure of any potential o(β)-approximation algorithm.

AB - Let G=(V,E,w) be a Δβ-metric graph with a distance function w(⋅,⋅) on V such that w(v,v)=0, w(u,v)=w(v,u), and w(u,v)≤β⋅(w(u,x)+w(x,v)) for all u,v,x∈V. Given a positive integer p, let H be a spanning subgraph of G satisfying the conditions that vertices (hubs) in C⊂V form a clique of size at most p in H, vertices (non-hubs) in V∖C form an independent set in H, and each non-hub v∈V∖C is adjacent to exactly one hub in C. Define dH(u,v)=w(u,f(u))+w(f(u),f(v))+w(v,f(v)) where f(u) and f(v) are hubs adjacent to u and v in H respectively. Notice that if u is a hub in H then w(u,f(u))=0. Let r(H)=∑u,v∈VdH(u,v) be the routing cost of H. The SINGLE ALLOCATION AT MOST p-HUB CENTER ROUTING problem is to find a spanning subgraph H of G such that r(H) is minimized. 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. Finally, we show that the approximation ratio of our algorithms is at least Ω(β), and we examine the structure of any potential o(β)-approximation algorithm.

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

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

U2 - 10.1016/j.tcs.2019.05.008

DO - 10.1016/j.tcs.2019.05.008

M3 - Article

AN - SCOPUS:85066240262

VL - 806

SP - 271

EP - 280

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -