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 -> a"currency sign(+), a set T (1),T (2),aEuro broken vertical bar,T (k) of subtrees of G is called a tree cover of G if . 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 Arkin et al. (J. Algorithms 59:1-18, 2006) and Even et al. (Oper. Res. Lett. 32(4):309-315, 2004) with ratio 4. The problem is known to have an APX-hardness lower bound of (Xu and Wen in Oper. Res. Lett. 38:169-173, 2010). In the Bounded Tree Cover problem we are given graph G and a bound lambda and the goal is to find a tree cover with minimum number of trees such that each tree has weight at most lambda. We present a 2.5-approximation algorithm for this, improving the 3-approximation bound in Arkin et al. (J. Algorithms 59:1-18, 2006).