An Approximation Algorithm for the p-Hub Median Problem

In the p-hub median problem we are given a set of clients V, a set of demands D⊆V×V, a cost function ρ:V×V→R+, and an integer p>0. The objective is to select terminals T⊆V, where |T|≤p, and assign each demand to a terminal, in order to minimize the total cost between demands and terminals. We present the first approximation bounds for the problem: a 1+2/e lower bound if NP⊂DTIME(nO(log⁡log⁡n)), and a (4α)-approximation algorithm if we are allowed to open at most (2α2α−1)p terminals, where α>1 is a trade off parameter.