Balanced partition of minimum spanning trees
(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:
https://lup.lub.lu.se/record/303923
- author
- Andersson, Mattias LU ; Gudmundsson, J ; Levcopoulos, Christos LU and Narasimhan, G
- organization
- publishing date
- 2003
- 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}}, }