類  型 演講活動
 張貼日期 0000-00-00
 發佈人員 系辦
 附  件

講題(topic):Approximability of Hub Allocation Problems
Given a metric graph G = (V, E, w), a center c, and an integer p, the Star p-Hub Center problem is to find a depth-2 spanning tree T of G rooted at c such that c has exactly p children and the diameter of T is minimized. Those children of c in T are called hubs. A similar problem called the Single Allocation p-Hub Center problem is to find a spanning subgraph H* of G such that (i) C* is a clique of size p 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 p-Hub Center problem and Single Allocation p-Hub Center problem are NP-hard and have applications in transportation system, telecommunication system, and post mail system. In this talk, I will give 5/3-approximation algorithms for both problems. Moreover, I will give a proof to show that for any  > 0, both problems have no (1.5 )-approximation algorithms unless P = NP. Suppose that the input graph G = (V, E, w) is a -metric, for some  ≥ 1/2, which satisfies the -triangle inequality, i.e., w(u, v) ≤  (w(u, x) + w(x, v)) for all vertices u,v,xV. We can further show that for any  > 0, to approximate the two hub allocation problems to a ratio g()   is NP-hard and
give r()-approximation algorithms where g() and r() are functions of .

( back 回上一頁)