Algorithms on Hub Allocation Problems

Given a metric graph g = (v; e; w), a center , and an integer k, the star k-hub center problem is tofind adepth-2 spanning tree t of g rooted by c such that c has exactly k children and the diameter of t isminimized. those children of c in t are called hubs. a similar problem called the single allocation k-hubcenter problem is to find a spanning subgraph h* of g such that (i) is a clique of size k in h*; (ii) formsan independent set in h*; (iii) each 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 haveapplications in transportation system, telecommunication system, and post mail system. in this talk, wegive 5 3-approximation algorithms for both problems. moreover, we prove that for any > 0 , the stark-hub center problem has no (1:5 − )-approximation algorithm unless p = np. under the assumptionp 6= np, for any > 0 the single allocation k-hub center problem has no ( 43)-approximation algorithm.