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.