Kinetic clustering of points on the line

Fernandes, Cristina G.; Oshiro, Marcio T. I.

Advanced search

Search - Use quotation marks to get a more specific result

Index

Field of knowledge

Start date

Betweenand

(Reference retrieved automatically from Web of Science through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

Kinetic clustering of points on the line

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

Short URL