Standard

On some finite set clustering problems in euclidean space. / Kel'Manov, Alexander; Pyatkin, Artem.

In: CEUR Workshop Proceedings, Vol. 1987, 01.01.2017, p. 310-315.

Research output: Contribution to journal › Conference article › peer-review

Harvard

Kel'Manov, A & Pyatkin, A 2017, 'On some finite set clustering problems in euclidean space', CEUR Workshop Proceedings, vol. 1987, pp. 310-315.

APA

Kel'Manov, A., & Pyatkin, A. (2017). On some finite set clustering problems in euclidean space. CEUR Workshop Proceedings, 1987, 310-315.

Vancouver

Kel'Manov A, Pyatkin A. On some finite set clustering problems in euclidean space. CEUR Workshop Proceedings. 2017 Jan 1;1987:310-315.

Author

Kel'Manov, Alexander ; Pyatkin, Artem. / On some finite set clustering problems in euclidean space. In: CEUR Workshop Proceedings. 2017 ; Vol. 1987. pp. 310-315.

BibTeX

@article{1702a39512b94817aae4a7824e57f39b,
title = "On some finite set clustering problems in euclidean space",
abstract = "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).",
author = "Alexander Kel'Manov and Artem Pyatkin",
year = "2017",
month = jan,
day = "1",
language = "English",
volume = "1987",
pages = "310--315",
journal = "CEUR Workshop Proceedings",
issn = "1613-0073",
publisher = "CEUR-WS",

}

RIS

TY - JOUR

T1 - On some finite set clustering problems in euclidean space

AU - Kel'Manov, Alexander

AU - Pyatkin, Artem

PY - 2017/1/1

Y1 - 2017/1/1

N2 - 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).

AB - 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).

UR - http://www.scopus.com/inward/record.url?scp=85036671238&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:85036671238

VL - 1987

SP - 310

EP - 315

JO - CEUR Workshop Proceedings

JF - CEUR Workshop Proceedings

SN - 1613-0073

ER -

ID: 10066063