We analyze the tour partitioning heuristics for the Capacitated Minimum Spanning Tree problem. Lower bounds for the worst-case performance ratios of these heuristics are obtained by using worst-case examples. We also generalize the heuristics to the multi-center case with the same worst-case bounds. Baltzer A.G. Scientific Publishing Company.
ASJC Scopus subject areas
- Management Science and Operations Research
- Decision Sciences(all)