Approximation algorithms for solving the heterogeneous rooted tree/path cover problems

In this paper, we consider the heterogeneous rooted tree cover (HRTC) problem, which further generalizes the rooted tree cover problem. Specifically, given a complete graph $$G=(V,E; w,f; r)$$ G = ( V , E ; w , f ; r ) and k construction teams, having nonuniform construction speeds $$\lambda _{1}$$ λ 1 , $$\lambda _{2}$$ λ 2 , $$\ldots $$ … , $$\lambda _{k}$$ λ k , where $$r\in V$$ r ∈ V is a fixed common root, $$w:E\rightarrow {\mathbb {R}}^{+}$$ w : E → R + is an edge-weight function, satisfying the triangle inequality, and $$f:V\rightarrow {\mathbb {R}}^{+}_{0}$$ f : V → R 0 + (i.e., $${\mathbb {R}}^{+}\cup \{0\})$$ R + ∪ { 0 } ) is a vertex-weight function with $$f(r)=0$$ f ( r ) = 0 , we are asked to find k trees for these k construction teams, each tree having the same root r, and collectively covering all vertices in V, the objective is to minimize the maximum completion time of k construction teams, where the completion time of each team is the total construction weight of its related tree divided by its construction speed. In addition, substituting k paths for k trees in the HRTC problem, we also consider the heterogeneous rooted path cover (HRPC) problem. Our main contributions are as follows. (1) Given any small constant $$\delta >0$$ δ > 0 , we first design a $$58.3286(1+\delta )$$ 58.3286 ( 1 + δ ) -approximation algorithm to solve the HRTC problem, and this algorithm runs in time $$O(n^{2}(n+\frac{\log n}{\delta })+\log (w(E)+f(V)))$$ O ( n 2 ( n + log n δ ) + log ( w ( E ) + f ( V ) ) ) . Meanwhile, we present a simple $$116.6572(1+\delta )$$ 116.6572 ( 1 + δ ) -approximation algorithm to solve the HRPC problem, whose time complexity is the same as the preceding algorithm. (2) We provide a $$\max \{2\rho , 2+\rho -\frac{2}{k}\}$$ max { 2 ρ , 2 + ρ - 2 k } -approximation algorithm to resolve the HRTC problem, and that algorithm runs in time $$O(n^{2})$$ O ( n 2 ) , where $$\rho $$ ρ is the ratio of the largest team speed to the smallest one. At the same time, we can prove that the preceding $$\max \{2\rho , 2+\rho -\frac{2}{k}\}$$ max { 2 ρ , 2 + ρ - 2 k } -approximation algorithm also resolves the HRPC problem.