Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

Kinetic clustering of points on the line

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
Linha de fomento: Auxílio à Pesquisa - Temático