Approximation Algorithms for Min-Max Path Cover Problems with Service Handling Time.

This paper presents improved approximation algorithms and inapproximability results for min-max path cover problems with service handling time, which have wide applications in practice when the latest service completion time for customers is critical. We study three variants of this problem, where paths must start (i) from a given depot, (ii) from any depot of a given set, and (iii) from any vertex of the given graph, respectively. For these three variants, we are able to achieve approximation ratios of 3, (4 + ε), and (5 + ε), respectively, for any ε> 0. We have further shown that approximation ratios less than 4/3, 3/2, and 3/2 are impossible for them, respectively, unless NP = P. [ABSTRACT FROM AUTHOR]