Conferences in Research and Practice in Information Technology
  

Online Version - Last Updated - 20 Jan 2012

 

 
Home
 

 
Procedures and Resources for Authors

 
Information and Resources for Volume Editors
 

 
Orders and Subscriptions
 

 
Published Articles

 
Upcoming Volumes
 

 
Contact Us
 

 
Useful External Links
 

 
CRPIT Site Search
 
    

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