We study the min-size $k$-clustering problem, a geometric clustering problem which generalizes clustering to minimize the sum of diameters or radii. We prove that the problem can be solved in polynomial time when the points to be clustered are located on a line. For higher dimensions, we show that the problem is NP-hard and present polynomial time approximation schemes.
Geometric clustering to minimize the sum of cluster sizes
BILO', VITTORIO;
2005-01-01
Abstract
We study the min-size $k$-clustering problem, a geometric clustering problem which generalizes clustering to minimize the sum of diameters or radii. We prove that the problem can be solved in polynomial time when the points to be clustered are located on a line. For higher dimensions, we show that the problem is NP-hard and present polynomial time approximation schemes.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
