Balanced partition of minimum spanning trees
Author
Summary, in English
To better handle situations where additional resources are available to carry out a task, many problems from the manufacturing industry involve dividing a task into a number of smaller tasks, while optimizing a specific objective function. In this paper we consider the problem of partitioning a given set S of n points in the plane into k subsets, S-1,...,S-k, such that max(1less than or equal toiless than or equal tok) MST(S-i) is minimized. Variants of this problem arise in applications from the shipbuilding industry. We show that this problem is NP-hard, and we also present an approximation algorithm for the problem, in the case when k is a fixed constant. The approximation algorithm runs in time O(n logn) and produces a partition that is within a factor (4/3 + epsilon) of the optimal if k = 2, and a factor (2 + epsilon) otherwise.
Department/s
- Computer Science
Publishing year
2003
Language
English
Pages
303-316
Publication/Series
International Journal of Computational Geometry and Applications
Volume
13
Issue
4
Document type
Journal article
Publisher
World Scientific Publishing
Topic
- Computer Science
Keywords
- approximation algorithms
- computational geometry
Status
Published
Project
- VR 2002-4049
ISBN/ISSN/Other
- ISSN: 0218-1959