Easy NP-hardness Proofs of Some Subset Choice Problems

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

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.

Original languageEnglish
Title of host publicationMathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Revised Selected Papers
EditorsYury Kochetov, Igor Bykadorov, Tatiana Gruzdeva
PublisherSpringer Science and Business Media Deutschland GmbH
Pages70-79
Number of pages10
ISBN (Print)9783030586560
DOIs
Publication statusPublished - Jul 2020
Event19th International Conference on Mathematical Optimization Theory and Operations Research,MOTOR 2020 - Novosibirsk, Russian Federation
Duration: 6 Jul 202010 Jul 2020

Publication series

NameCommunications in Computer and Information Science
Volume1275 CCIS
ISSN (Print)1865-0929
ISSN (Electronic)1865-0937

Conference

Conference19th International Conference on Mathematical Optimization Theory and Operations Research,MOTOR 2020
CountryRussian Federation
CityNovosibirsk
Period06.07.202010.07.2020

Keywords

  • 2-partition
  • Clustering
  • Euclidean space
  • Strong np-hardness
  • Subset choice

Fingerprint

Dive into the research topics of 'Easy NP-hardness Proofs of Some Subset Choice Problems'. Together they form a unique fingerprint.

Cite this