Analysis of heuristics for the design of tree networks

Bezalel Gavish, Chung Lun Li, David Simchi-Levi

Research output: Journal article publicationJournal articleAcademic researchpeer-review

5 Citations (Scopus)

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 languageEnglish
Pages (from-to)77-86
Number of pages10
JournalAnnals of Operations Research
Volume36
Issue number1
DOIs
Publication statusPublished - 1 Dec 1992
Externally publishedYes

ASJC Scopus subject areas

  • Management Science and Operations Research
  • Decision Sciences(all)

Cite this