Improved Approximation Algorithms for the Min-Max Tree Cover and Bounded Tree Cover Problems

摘要

In this paper we provide improved approximation algorithms for the Min-Max Tree Cover and Bounded Tree Cover problems. Given a graph G = (V, E) with weights w : E → N~+, a set T_1,T_2,...,T_k of subtrees of G is called a tree cover of G if V = ∪_(i=1)~k V(T_i). In the Min Max k-tree Cover problem we are given graph G and a positive integer k and the goal is to find a tree cover with k trees, such that the weight of the largest tree in the cover is minimized. We present a 3-approximation algorithm for this improving the two different approximation algorithms presented in [1,5] with ratio 4. The problem is known to have an APX-hardness lower bound of 3/2 [12]. In the Bounded Tree Cover problem we are given graph G and a bound λ and the goal is to find a tree cover with minimum number of trees such that each tree has weight at most λ. We present a 2.5-approximation algorithm for this, improving the 3-approximation bound in [1].