Du är här

Balanced partition of minimum spanning trees

Författare:
Publiceringsår: 2003
Språk: Engelska
Sidor: 303-316
Publikation/Tidskrift/Serie: International Journal of Computational Geometry & Applications
Volym: 13
Nummer: 4
Dokumenttyp: Artikel
Förlag: World Scientific Publishing Company

Sammanfattning

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.

Disputation

Nyckelord

  • Technology and Engineering
  • Mathematics and Statistics
  • approximation algorithms
  • computational geometry

Övriga

Published
  • VR 2002-4049
Yes
  • ISSN: 0218-1959

Box 117, 221 00 LUND
Telefon 046-222 00 00 (växel)
Telefax 046-222 47 20
lu [at] lu [dot] se

LERU logotype U21 logotype

Fakturaadress: Box 188, 221 00 LUND
Organisationsnummer: 202100-3211
Om webbplatsen