Standard

Easy NP-hardness Proofs of Some Subset Choice Problems. / Pyatkin, Artem V.

Mathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Revised Selected Papers. ред. / Yury Kochetov; Igor Bykadorov; Tatiana Gruzdeva. Springer Science and Business Media Deutschland GmbH, 2020. стр. 70-79 (Communications in Computer and Information Science; Том 1275 CCIS).

Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование

Harvard

Pyatkin, AV 2020, Easy NP-hardness Proofs of Some Subset Choice Problems. в Y Kochetov, I Bykadorov & T Gruzdeva (ред.), Mathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Revised Selected Papers. Communications in Computer and Information Science, Том. 1275 CCIS, Springer Science and Business Media Deutschland GmbH, стр. 70-79, 19th International Conference on Mathematical Optimization Theory and Operations Research,MOTOR 2020, Novosibirsk, Российская Федерация, 06.07.2020. https://doi.org/10.1007/978-3-030-58657-7_8

APA

Pyatkin, A. V. (2020). Easy NP-hardness Proofs of Some Subset Choice Problems. в Y. Kochetov, I. Bykadorov, & T. Gruzdeva (Ред.), Mathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Revised Selected Papers (стр. 70-79). (Communications in Computer and Information Science; Том 1275 CCIS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-030-58657-7_8

Vancouver

Pyatkin AV. Easy NP-hardness Proofs of Some Subset Choice Problems. в Kochetov Y, Bykadorov I, Gruzdeva T, Редакторы, Mathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Revised Selected Papers. Springer Science and Business Media Deutschland GmbH. 2020. стр. 70-79. (Communications in Computer and Information Science). doi: 10.1007/978-3-030-58657-7_8

Author

Pyatkin, Artem V. / Easy NP-hardness Proofs of Some Subset Choice Problems. Mathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Revised Selected Papers. Редактор / Yury Kochetov ; Igor Bykadorov ; Tatiana Gruzdeva. Springer Science and Business Media Deutschland GmbH, 2020. стр. 70-79 (Communications in Computer and Information Science).

BibTeX

@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",

}

RIS

TY - GEN

T1 - Easy NP-hardness Proofs of Some Subset Choice Problems

AU - Pyatkin, Artem V.

PY - 2020/7

Y1 - 2020/7

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

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

KW - 2-partition

KW - Clustering

KW - Euclidean space

KW - Strong np-hardness

KW - Subset choice

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

U2 - 10.1007/978-3-030-58657-7_8

DO - 10.1007/978-3-030-58657-7_8

M3 - Conference contribution

AN - SCOPUS:85092118819

SN - 9783030586560

T3 - Communications in Computer and Information Science

SP - 70

EP - 79

BT - Mathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Revised Selected Papers

A2 - Kochetov, Yury

A2 - Bykadorov, Igor

A2 - Gruzdeva, Tatiana

PB - Springer Science and Business Media Deutschland GmbH

T2 - 19th International Conference on Mathematical Optimization Theory and Operations Research,MOTOR 2020

Y2 - 6 July 2020 through 10 July 2020

ER -

ID: 25676691