@inproceedings{a7c55f74547c4c1592a0289cdbf4efba,
title = "Easy NP-hardness Proofs of Some Subset Choice Problems",
abstract = "We consider the following subset choice problems: given a family of Euclidean vectors, find a subset having the largest a) norm of the sum of its elements; b) square of the norm of the sum of its elements divided by the cardinality of the subset. The NP-hardness of these problems was proved in two papers about ten years ago by reduction of 3-SAT problem. However, that proofs were very tedious and hard to read. In the current paper much easier and natural proofs are presented.",
keywords = "2-partition, Clustering, Euclidean space, Strong np-hardness, Subset choice",
author = "Pyatkin, {Artem V.}",
year = "2020",
month = jul,
doi = "10.1007/978-3-030-58657-7_8",
language = "English",
isbn = "9783030586560",
series = "Communications in Computer and Information Science",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "70--79",
editor = "Yury Kochetov and Igor Bykadorov and Tatiana Gruzdeva",
booktitle = "Mathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Revised Selected Papers",
address = "Germany",
note = "19th International Conference on Mathematical Optimization Theory and Operations Research,MOTOR 2020 ; Conference date: 06-07-2020 Through 10-07-2020",
}