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

Li Hsuan Chen, Sun-Yuan Hsieh, Ling Ju Hung, Ralf Klasing

Research output: Contribution to journalArticle

Abstract

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.

Original languageEnglish
JournalTheoretical Computer Science
DOIs
Publication statusPublished - 2019 Jan 1

Fingerprint

Metric Graphs
Center Problem
Spanning Subgraph
Routing Problem
Approximation algorithms
Approximation Algorithms
Adjacent
Distance Function
Independent Set
Clique
Computational complexity
Routing
NP-complete problem
Integer
Costs
Approximation
Graph in graph theory
Form

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

@article{229566438acf4a99aeaf3f9c1a9f29c7,
title = "Approximation algorithms for the p-hub center routing problem in parameterized metric graphs",
abstract = "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.",
author = "Chen, {Li Hsuan} and Sun-Yuan Hsieh and Hung, {Ling Ju} and Ralf Klasing",
year = "2019",
month = "1",
day = "1",
doi = "10.1016/j.tcs.2019.05.008",
language = "English",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",

}

Approximation algorithms for the p-hub center routing problem in parameterized metric graphs. / Chen, Li Hsuan; Hsieh, Sun-Yuan; Hung, Ling Ju; Klasing, Ralf.

In: Theoretical Computer Science, 01.01.2019.

Research output: Contribution to journalArticle

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

PY - 2019/1/1

Y1 - 2019/1/1

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

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -