Easy NP-hardness Proofs of Some Subset Choice Problems

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

Аннотация

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.

Язык оригиналаанглийский
Название основной публикации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
Страницы70-79
Число страниц10
ISBN (печатное издание)9783030586560
DOI
СостояниеОпубликовано - июл 2020
Событие19th International Conference on Mathematical Optimization Theory and Operations Research,MOTOR 2020 - Novosibirsk, Российская Федерация
Продолжительность: 6 июл 202010 июл 2020

Серия публикаций

НазваниеCommunications in Computer and Information Science
Том1275 CCIS
ISSN (печатное издание)1865-0929
ISSN (электронное издание)1865-0937

Конференция

Конференция19th International Conference on Mathematical Optimization Theory and Operations Research,MOTOR 2020
СтранаРоссийская Федерация
ГородNovosibirsk
Период06.07.202010.07.2020

Fingerprint Подробные сведения о темах исследования «Easy NP-hardness Proofs of Some Subset Choice Problems». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать