NP-Hardness of Some Euclidean Problems of Partitioning a Finite Set of Points

Standard

NP-Hardness of Some Euclidean Problems of Partitioning a Finite Set of Points. / Kel’manov, A. V.; Pyatkin, A. V.

In: Computational Mathematics and Mathematical Physics, Vol. 58, No. 5, 01.05.2018, p. 822-826.

Research output: Contribution to journal › Article › peer-review

Harvard

Kel’manov, AV & Pyatkin, AV 2018, 'NP-Hardness of Some Euclidean Problems of Partitioning a Finite Set of Points', Computational Mathematics and Mathematical Physics, vol. 58, no. 5, pp. 822-826. https://doi.org/10.1134/S0965542518050123

APA

Kel’manov, A. V., & Pyatkin, A. V. (2018). NP-Hardness of Some Euclidean Problems of Partitioning a Finite Set of Points. Computational Mathematics and Mathematical Physics, 58(5), 822-826. https://doi.org/10.1134/S0965542518050123

Vancouver

Kel’manov AV, Pyatkin AV. NP-Hardness of Some Euclidean Problems of Partitioning a Finite Set of Points. Computational Mathematics and Mathematical Physics. 2018 May 1;58(5):822-826. doi: 10.1134/S0965542518050123

Author

Kel’manov, A. V. ; Pyatkin, A. V. / NP-Hardness of Some Euclidean Problems of Partitioning a Finite Set of Points. In: Computational Mathematics and Mathematical Physics. 2018 ; Vol. 58, No. 5. pp. 822-826.

BibTeX

@article{f07fd80a28f641d2865b04e0900bbb6a,

title = "NP-Hardness of Some Euclidean Problems of Partitioning a Finite Set of Points",

abstract = "Problems of partitioning a finite set of Euclidean points (vectors) into clusters are considered. The criterion is to minimize the sum, over all clusters, of (1) squared norms of the sums of cluster elements normalized by the cardinality, (2) squared norms of the sums of cluster elements, and (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 are 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).",

keywords = "Euclidean space, norm of sum, NP-hardness, partitioning",

author = "Kel{\textquoteright}manov, {A. V.} and Pyatkin, {A. V.}",

note = "Publisher Copyright: {\textcopyright} 2018, Pleiades Publishing, Ltd.",

year = "2018",

month = may,

day = "1",

doi = "10.1134/S0965542518050123",

language = "English",

volume = "58",

pages = "822--826",

journal = "Computational Mathematics and Mathematical Physics",

issn = "0965-5425",

publisher = "PLEIADES PUBLISHING INC",

number = "5",

}

RIS

TY - JOUR

T1 - NP-Hardness of Some Euclidean Problems of Partitioning a Finite Set of Points

AU - Kel’manov, A. V.

AU - Pyatkin, A. V.

PY - 2018/5/1

Y1 - 2018/5/1

N2 - Problems of partitioning a finite set of Euclidean points (vectors) into clusters are considered. The criterion is to minimize the sum, over all clusters, of (1) squared norms of the sums of cluster elements normalized by the cardinality, (2) squared norms of the sums of cluster elements, and (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 are 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 to minimize the sum, over all clusters, of (1) squared norms of the sums of cluster elements normalized by the cardinality, (2) squared norms of the sums of cluster elements, and (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 are 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).

KW - Euclidean space

KW - norm of sum

KW - NP-hardness

KW - partitioning

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

U2 - 10.1134/S0965542518050123

DO - 10.1134/S0965542518050123

M3 - Article

AN - SCOPUS:85048616703

VL - 58

SP - 822

EP - 826

JO - Computational Mathematics and Mathematical Physics

JF - Computational Mathematics and Mathematical Physics

SN - 0965-5425

IS - 5

ER -

ID: 14048528