On some finite set clustering problems in euclidean space

Alexander Kel'Manov, Artem Pyatkin

Результат исследования: Научные публикации в периодических изданияхстатья по материалам конференциирецензирование

Аннотация

Problems of partitioning a finite set of Euclidean points (vectors) into clusters are considered. The criterion is minimizing the sum over all clusters of: (1) normalized by the cardinality squared norms of the sum of cluster elements, (2) squared norms of the sum of cluster elements, (3) norms of the sum of cluster elements. It is proved that all these problems are strongly NP-hard if the number of clusters is a part of the input, and NP-hard in the ordinary sense if the number of clusters is not a part of the input (is fixed). Moreover, the problems are NP-hard even in the case of dimension 1 (on a line).

Язык оригиналаанглийский
Страницы (с-по)310-315
Число страниц6
ЖурналCEUR Workshop Proceedings
Том1987
СостояниеОпубликовано - 1 янв 2017

Fingerprint Подробные сведения о темах исследования «On some finite set clustering problems in euclidean space». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать