Abstract
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.
Original language | English |
---|---|
Pages (from-to) | 77-86 |
Number of pages | 10 |
Journal | Annals of Operations Research |
Volume | 36 |
Issue number | 1 |
DOIs | |
Publication status | Published - 1 Dec 1992 |
Externally published | Yes |
ASJC Scopus subject areas
- Management Science and Operations Research
- General Decision Sciences