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 set T 1,T 2,,T k of subtrees of G is called a tree cover of G if \(V=\bigcup_{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 Arkin etal. (J. Algorithms 59:118, 2006) and Even etal. (Oper. Res. Lett. 32(4):309315, 2004) with ratio 4. The problem is known to have an APX-hardness lower bound of \(\frac{3}{2}\) (Xu and Wen in Oper. Res. Lett. 38:169173, 2010). 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 Arkin etal. (J. Algorithms 59:118, 2006).
approximation algorithms min-max tree cover bounded tree cover