| Full text | |
| Author(s): |
Fernandes, Cristina G.
;
Oshiro, Marcio T. I.
Total Authors: 2
|
| Document type: | Journal article |
| Source: | THEORETICAL COMPUTER SCIENCE; v. 639, p. 60-71, AUG 1 2016. |
| Web of Science Citations: | 0 |
| Abstract | |
The problem of clustering a set of points moving on the line consists of the following: given positive integers n and k, the initial position and the velocity of n points, find an optimal k-clustering of the points. We consider two classical quality measures for the clustering: minimizing the sum of the clusters diameters and minimizing the maximum diameter of a cluster. For the former, we present polynomial-time algorithms under some assumptions and, for the latter, a (2.71 + epsilon) -approximation. (C) 2016 Elsevier B.V. All rights reserved. (AU) | |
| FAPESP's process: | 13/03447-6 - Combinatorial structures, optimization, and algorithms in theoretical Computer Science |
| Grantee: | Carlos Eduardo Ferreira |
| Support Opportunities: | Research Projects - Thematic Grants |