טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentRoman Shpiegelman
SubjectApproximation Algorithms for Multicast K-Tree
Routing Problem
DepartmentDepartment of Industrial Engineering and Management
Supervisor
Full Thesis textFull thesis text - English Version


Abstract

In this work we will study the Multicast k-Tree Routing problem, namely kMTR.

In a sequence of papers, the approximation ratio for this problem was improved from 4 to the current best 3.233.

All these algorithms are purely combinatorial.

In the main part of our work we will suggest a random algorithm that has approximation ratio of  3.079 for  every fixed value of k.

We will first refine the performance analysis of the deterministic approximation algorithm suggested by Cai Lin and Xue.

We will improve its approximation ratio for odd values of k.

We will use this algorithm as a sub-routine in our random algorithm.

Then we will also suggest a deterministic algorithm

which provides the best approximation ratio for k=3,4,5,6.

We will also prove that the problem is NP-HARD for k=3.

Then we will suggest a polynomial randomized rounding algorithm for fixed values of k.

We will show that the expected approximation ratio of our algorithm is not more than 3.079 for every fixed value of k.

For small values of k we will show that our algorithm provides a better approximation ratio than the general case approximation ratio of 3.079.