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.
- Inapproximability bound
- Tree covers
- Vehicle routing
ASJC Scopus subject areas
- Management Science and Operations Research
- Industrial and Manufacturing Engineering
- Applied Mathematics