M.Sc Thesis
M.Sc Student Rozenfeld Stas Approximation Algorithm for the Group Steiner Network Problem Department of Industrial Engineering and Management Professor Michal Penn

Abstract

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 .