Approximation Algorithms for Min-Max Capacitated Path Covers

Xu, Z. and Xu, L.

    This paper presents the first approximation algorithms and the first inapproximability results for min- max path cover problems, where a capacity constraint restricts the number of customers that can be serviced by every trip of the paths in the cover. Depending on different applications, every path in the cover may either be restricted to contain only one trip, or be allowed to contain multiple trips but with a return to the depot between every two consecutive trips. We develop a 5-approximation algorithm for the problem with multiple trips allowed, and a (7 + ε)-approximation algorithm for any ε > 0 for the problem with single trips only. For both problems, we show that unless NP = P, it is impossible to achieve any performance ratios less than 3/2.
Cite as: Xu, Z. and Xu, L. (2010). Approximation Algorithms for Min-Max Capacitated Path Covers. In Proc. 16-th Computing: The Australasian Theory Symposium (CATS 2010) Brisbane, Australia. CRPIT, 109. Viglas, T. and Potanin, A. Eds., ACS. 11-18
pdf (from crpit.com) pdf (local if available) BibTeX EndNote GS