The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

Balanced partition of minimum spanning trees

På svenska

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