Goal of the Project
In this project, we plan to study the following problems from the view point of approximation algorithms. Rooted Min-Max Tree Cover (RMMTC): We are given an undirected graph G with non-negative edge lengths, a pre-specified multiset of root vertices R and a positive integer k. We wish to find a set of k sub-trees of G, each containing a unique vertex from R, such that every vertex of G is contained in at least one of these k trees. The objective is to minimize the maximum cost among all the trees.
This problem generalises the Minimum Makespan Scheduling and is already NP-Hard when G is a star and |R|=1. Even et al. [1] gave a 4-approximation algorithm for RMMTC and it has not been improved since. There have been improvements in the approximation ratio for some special cases, but the general problem still remains open. The goal of the project is to improve upon this approximation factor. We will begin by looking at the special case when R is a singleton. We already have preliminary ideas on improving the approximation guarantee in this case and hope to improve the approximation ratio further by pushing these ideas and coming up with new ones.
We will also study a closely related problem, called the Rooted Min Max Tour Cover, where instead of trees we wish to find closed walks starting and ending at r. There are many other closely related variants of this problem as well (see [2]) and we hope that the ideas developed in the context of RMMTC will be useful in developing improved approximation algorithms for these as well. We also plan to evaluate the performance of the proposed algorithms through experimental simulations.
