|M.Sc Student||Rozenfeld Stas|
|Subject||Approximation Algorithm for the Group Steiner Network|
|Department||Department of Industrial Engineering and Management||Supervisor||Professor Michal Penn|
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 .