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

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

研究成果: Conference contribution

1 引文 斯高帕斯(Scopus)

摘要

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.

原文English
主出版物標題Combinatorial Algorithms - 29th International Workshop, IWOCA 2018, Proceedings
編輯Hon Wai Leong, Costas Iliopoulos, Wing-Kin Sung
發行者Springer Verlag
頁面115-127
頁數13
ISBN(列印)9783319946665
DOIs
出版狀態Published - 2018
事件29th International Workshop on Combinatorial Algorithms, IWOCA 2018 - Singapore, Singapore
持續時間: 2018 七月 162018 七月 19

出版系列

名字Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
10979 LNCS
ISSN(列印)0302-9743
ISSN(電子)1611-3349

Other

Other29th International Workshop on Combinatorial Algorithms, IWOCA 2018
國家Singapore
城市Singapore
期間18-07-1618-07-19

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

指紋 深入研究「Approximation algorithms for the p-hub center routing problem in parameterized metric graphs」主題。共同形成了獨特的指紋。

引用此