Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
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).Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
}
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