M.Sc Student | Stas Rozenfeld |
---|---|

Subject | Approximation Algorithm for the Group Steiner Network Problem |

Department | Department of Industrial Engineering and Management |

Supervisor | Professor Penn Michal |

In this research we define
and study the *Minimum Group Steiner Network Problem*. In this problem we
are given a weighted undirected graph _{}, a partition of its vertices _{} into _{} vertex groups,
and a symmetric pair-group connectivity function _{}. The aim is to choose
simultaneously a set of *representatives*, one representative for each
group, say _{} for
_{}, and
to find a network of minimum cost, possibly with multiple edges, with _{} edge-disjoint
paths between _{} and _{} for all _{}.

Our problem is a
generalization of the *minimum group Steiner tree problem* and the *minimum
Steiner network problem*, therefore it is NP-hard.

We present an approximation
algorithm for the group Steiner network problem that consists of two
algorithms. Our algorithm solves the minimum group Steiner network problem by
choosing the best out of the obtained solutions of the two algorithms. The
first algorithm (Algorithm 1) uses linear programming to find a set of
representatives and then solves minimum Steiner network problem using Jain's
Algorithm. For this algorithm we assume that each group has an associated group
connectivity type _{} and that the pair-group connectivity
requirement function has the following form: _{}. Algorithm 1 attains an
approximation ratio of _{}, where _{} is the cardinality of a
largest group. In the second one (Algorithm 2) the part developed in this work
is combinatorial. Algorithm 2 uses Jain's Algorithm too, therefore it uses LP
as well. Here we first find the external structure of the solution, and then
chooses a set of representatives. For Algorithm 2 we assume that each _{} induces a
complete graph. Algorithm 2 gives an approximation ratio of _{}, where _{} depends on the
cost function. Thus our main algorithm has an approximation ratio of _{}.