𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A 3/2-approximation algorithm for -partitioning

✍ Scribed by Hans Kellerer; Vladimir Kotov

Book ID
113834550
Publisher
Elsevier Science
Year
2011
Tongue
English
Weight
231 KB
Volume
39
Category
Article
ISSN
0167-6377

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Approximation Algorithms for Min–Max Tre
Approximation Algorithms for Min–Max Tree Partition
✍ Nili Guttmann-Beck; Refael Hassin πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 298 KB

We consider the problem of partitioning the node set of a graph into p equal sized subsets. The objective is to minimize the maximum length, over these subsets, of a minimum spanning tree. We show that no polynomial algorithm with bounded Ε½ 2 . error ratio can be given for the problem unless P s NP.