Abstract: This research presents the first constant approximation
algorithm to the p-median network design problem with multiple
cable types. This problem was addressed with a single cable type and
there is a bifactor approximation algorithm for the problem. To the
best of our knowledge, the algorithm proposed in this paper is the first
constant approximation algorithm for the p-median network design
with multiple cable types. The addressed problem is a combination of
two well studied problems which are p-median problem and network
design problem. The introduced algorithm is a random sampling
approximation algorithm of constant factor which is conceived by
using some random sampling techniques form the literature. It is
based on a redistribution Lemma from the literature and a steiner tree
problem as a subproblem. This algorithm is simple, and it relies on the
notions of random sampling and probability. The proposed approach
gives an approximation solution with one constant ratio without
violating any of the constraints, in contrast to the one proposed in the
literature. This paper provides a (21 + 2)-approximation algorithm
for the p-median network design problem with multiple cable types
using random sampling techniques.