Download as iCal file

Approximation algorithm for multicast k-tree routing problem

By Roman Spiegelman
Location Bloomfield 527
Advisor(s): Asaf Levin
MSc
Academic Program: OR
 
Sunday 12 November 2017, 14:30 - 15:30

In the Multicast k-Tree Routing Problem the input consists of the following parts: A simple, complete, undirected, weighted graph G with nodes set V,  a source node s and a set of destination nodes D (that is a subset of V). The weight of an edge represents its length.  Let k be a constant positive integer (and the value of k is a parameter of the problem). The goal is to find a partition of D into disjoint sets each of which of cardinality no more than k and for each subset in this partition to find a Steiner tree spanning the source node s and this subset of destination nodes (and perhaps additional nodes), so that the total length of these Steiner trees is minimized.

We use the randomized rounding technique to improve the known approximation ratios for this problem for all constant values of k.