 News & Events

# Approximation Algorithms on Some Network Optimization Problems

 日時 2019年8月27日(火) 10:30 – 12:00 北海道大学 電子科学研究所(北キャンパス総合研究棟5号館)1階　会議室 Chair Prof. Sun-Yuan Hsieh (スン ユエン シェ教授) National Cheng Kung University, Tainan, TaiwanDepartment of Computer Science and Information Engineering (国立成功大学（台湾）コンピュータサイエンス&情報工学科) Approximation Algorithms on Some Network Optimization Problems Given a metric graph G = (V, E, w), a center c ∈ V, and an integer k, the Star k-Hub Center Problem is to find adepth-2 spanning tree T of G rooted by c such that c has exactly k children and the diameter of T is minimized. Those children of c in T are called hubs. A similar problem called the Single Allocation k-Hub Center Problem is to find a spanning subgraph H* of G such that (i)C* is a clique of size k in H*; (ii)V \ C* forms an independent set in H*; (iii) each v ∈ V \ C* is adjacent to exactly one vertex in C*; and (iv) the diameter D(H*) is minimized. The vertices selected in C* are called hubs and the rest of vertices are called non-hubs. Both Star k-Hub Center Problem and Single Allocation k-Hub Center Problem are NP-hard and have applications in transportation system, telecommunication system, and post mail system. In this talk, we give 5/3-approximation algorithms for both problems. Moreover, we prove that for any ε > 0, the Star k -Hub Center Problem has no (1.5 − ε)-approximation algorithm unless P = NP. Under the assumption P ≠ NP, for any ε > 0 the Single Allocation k-Hub Center Problem has no (4/3 − ε)-approximation algorithm. 電子科学研究所学術交流委員会 北海道大学 電子科学研究所 ナノ構造物性研究分野 石橋 晃 電話：011-706-9423 ご案内【PDF】 