| Texto completo | |
| Autor(es): |
Fernandes, Cristina G.
;
Oshiro, Marcio T. I.
Número total de Autores: 2
|
| Tipo de documento: | Artigo Científico |
| Fonte: | THEORETICAL COMPUTER SCIENCE; v. 639, p. 60-71, AUG 1 2016. |
| Citações Web of Science: | 0 |
| Resumo | |
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) | |
| Processo FAPESP: | 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação |
| Beneficiário: | Carlos Eduardo Ferreira |
| Modalidade de apoio: | Auxílio à Pesquisa - Temático |