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

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.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11587/119073
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 53
  • ???jsp.display-item.citation.isi??? 36
social impact