Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Balanced partition of minimum spanning trees

Andersson, Mattias LU ; Gudmundsson, J ; Levcopoulos, Christos LU orcid 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
; ; and
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 Publishing
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
2016-04-01 16:29:34
date last changed
2022-01-28 20:06:49
@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}},
  keywords     = {{approximation algorithms; computational geometry}},
  language     = {{eng}},
  number       = {{4}},
  pages        = {{303--316}},
  publisher    = {{World Scientific Publishing}},
  series       = {{International Journal of Computational Geometry and Applications}},
  title        = {{Balanced partition of minimum spanning trees}},
  url          = {{http://dx.doi.org/10.1142/S0218195903001190}},
  doi          = {{10.1142/S0218195903001190}},
  volume       = {{13}},
  year         = {{2003}},
}