Analysis of heuristics for the design of tree networks

Bezalel Gavish; Chung Lun Li; David Simchi-Levi

doi:10.1007/BF02094324

Analysis of heuristics for the design of tree networks

Bezalel Gavish, Chung Lun Li, David Simchi-Levi

Research output: Journal article publication › Journal article › Academic research › peer-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 language	English
Pages (from-to)	77-86
Number of pages	10
Journal	Annals of Operations Research
Volume	36
Issue number	1
DOIs	https://doi.org/10.1007/BF02094324
Publication status	Published - 1 Dec 1992
Externally published	Yes

ASJC Scopus subject areas

Management Science and Operations Research
Decision Sciences(all)

More information

10.1007/BF02094324

Cite this

@article{3429ef47f1504ceb8b3ef6f3c320b285,

title = "Analysis of heuristics for the design of tree networks",

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.",

author = "Bezalel Gavish and Li, {Chung Lun} and David Simchi-Levi",

year = "1992",

month = dec,

day = "1",

doi = "10.1007/BF02094324",

language = "English",

volume = "36",

pages = "77--86",

journal = "Annals of Operations Research",

issn = "0254-5330",

publisher = "Springer Netherlands",

number = "1",

}

TY - JOUR

T1 - Analysis of heuristics for the design of tree networks

AU - Gavish, Bezalel

AU - Li, Chung Lun

AU - Simchi-Levi, David

PY - 1992/12/1

Y1 - 1992/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=34249841576&partnerID=8YFLogxK

U2 - 10.1007/BF02094324

DO - 10.1007/BF02094324

M3 - Journal article

SN - 0254-5330

VL - 36

SP - 77

EP - 86

JO - Annals of Operations Research

JF - Annals of Operations Research

IS - 1

ER -

Analysis of heuristics for the design of tree networks

Abstract

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this