Variations of the Optimal Clustering Tree Problem
We would like to present two variations, that we have studied recently, of the following general problem. Let G=(V,E) be a complete graph with a cost function on its edges and let S be a given collection of subsets of V. A spanning tree T is called a clustering tree (relative to S) if each subset of the vertices in S induces a subtree in T. Our problem is to find a minimum cost clustering tree T. We call this problem the OP problem. One motivation for this problem is to construct a minimum cost communication tree network for a collection of non-disjoint groups of customers such that the network will provide "group fault tolerance" and "group privacy". The first variation we consider is the clustering-TSP-path problem. In this case the input is the same as the input of the general problem. However, the tree that we would like to construct is a minimum cost TSP path. The problem in general is NP-hard and we solve some restricted cases. The second variation is the stars-OP problem, where again the input is the same as the input of the general problem. However, in this case we would like to construct a tree such that each subset induces a subtree that is a complete star. For this case we have proved a structure theorem that leads to a polynomial algorithm. We define another version of the clustering problem that we call the Median Optimization Problem (MOP), that can be stated as follows: the input of the problem is the same as the input of the OP problem. The output of the problem has to be a tree with the properties defined in each one of the problems above. However, the optimal solution is a tree with the above properties that minimizes the following objective function: for each subset in S we have a cost that is equal to the sum of the costs of the edges in the solution induced by this subset, and the value of the objective function is the sum of these costs. We find it interesting that for the general problem and for the stars case a tree is optimal for OP if and only if it is optimal for MOP. However, for the TSP-path case we provide an example that this is not true.
Joint work with Ephraim Korach.