Advanced

Balanced partition of minimum spanning trees

Andersson, Mattias LU ; Gudmundsson, J; Levcopoulos, Christos LU and Narasimhan, G (2003) In International Journal of Computational Geometry and Applications 13(4). p.303-316
Abstract
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... (More)
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. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
approximation algorithms, computational geometry
in
International Journal of Computational Geometry and Applications
volume
13
issue
4
pages
303 - 316
publisher
World Scientific
external identifiers
  • wos:000184726700003
  • scopus:0042361974
ISSN
0218-1959
DOI
10.1142/S0218195903001190
project
VR 2002-4049
language
English
LU publication?
yes
id
cfbeecb1-8047-44cd-910f-c876bcb93f6c (old id 303923)
date added to LUP
2007-08-22 12:08:46
date last changed
2017-01-01 07:06:48
@article{cfbeecb1-8047-44cd-910f-c876bcb93f6c,
  abstract     = {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.},
  author       = {Andersson, Mattias and Gudmundsson, J and Levcopoulos, Christos and Narasimhan, G},
  issn         = {0218-1959},
  keyword      = {approximation algorithms,computational geometry},
  language     = {eng},
  number       = {4},
  pages        = {303--316},
  publisher    = {World Scientific},
  series       = {International Journal of Computational Geometry and Applications},
  title        = {Balanced partition of minimum spanning trees},
  url          = {http://dx.doi.org/10.1142/S0218195903001190},
  volume       = {13},
  year         = {2003},
}