Approximation hardness of min–max tree covers

We prove the first inapproximability bounds to study approximation hardness for a min–max k-tree cover problem and its variants. The problem is to find a set of k trees to cover vertices of a given graph with metric edge weights, so as to minimize the maximum total edge weight of any of the k trees. Our technique can also be applied to improve inapproximability bounds for min–max problems that use other covering objectives, such as stars, paths, and tours.