RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Zh. Vychisl. Mat. Mat. Fiz.: Year: Volume: Issue: Page: Find

 Zh. Vychisl. Mat. Mat. Fiz., 2016, Volume 56, Number 10, Pages 1831–1836 (Mi zvmmf10476)

On the complexity and approximability of some Euclidean optimal summing problems

A. V. Eremeevab, A. V. Kel'manovac, A. V. Pyatkinac

a Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences, Novosibirsk, Russia
b Omsk State University, Omsk, Russia
c Novosibirsk State University, Novosibirsk, Russia

Abstract: The complexity status of several well-known discrete optimization problems with the direction of optimization switching from maximum to minimum is analyzed. The task is to find a subset of a finite set of Euclidean points (vectors). In these problems, the objective functions depend either only on the norm of the sum of the elements from the subset or on this norm and the cardinality of the subset. It is proved that, if the dimension of the space is a part of the input, then all these problems are strongly $\mathrm{NP}$-hard. Additionally, it is shown that, if the space dimension is fixed, then all the problems are $\mathrm{NP}$-hard even for dimension $2$ (on a plane) and there are no approximation algorithms with a guaranteed accuracy bound for them unless $\mathrm{P=NP}$. It is shown that, if the coordinates of the input points are integer, then all the problems can be solved in pseudopolynomial time in the case of a fixed space dimension.

Key words: Euclidean space, cluster analysis, search for a subset, norm of sum, $\mathrm{NP}$-hardness, pseudopolynomial solvability, discrete optimization problems.

 Funding Agency Grant Number Russian Foundation for Basic Research 15-01-00462_à15-01-00785_à15-01-00976_à

DOI: https://doi.org/10.7868/S0044466916100082

Full text: PDF file (146 kB)
References: PDF file   HTML file

English version:
Computational Mathematics and Mathematical Physics, 2016, 56:10, 1813–1817

Bibliographic databases:

UDC: 519.7

Citation: A. V. Eremeev, A. V. Kel'manov, A. V. Pyatkin, “On the complexity and approximability of some Euclidean optimal summing problems”, Zh. Vychisl. Mat. Mat. Fiz., 56:10 (2016), 1831–1836; Comput. Math. Math. Phys., 56:10 (2016), 1813–1817

Citation in format AMSBIB
\Bibitem{EreKelPya16} \by A.~V.~Eremeev, A.~V.~Kel'manov, A.~V.~Pyatkin \paper On the complexity and approximability of some Euclidean optimal summing problems \jour Zh. Vychisl. Mat. Mat. Fiz. \yr 2016 \vol 56 \issue 10 \pages 1831--1836 \mathnet{http://mi.mathnet.ru/zvmmf10476} \crossref{https://doi.org/10.7868/S0044466916100082} \elib{https://elibrary.ru/item.asp?id=26665214} \transl \jour Comput. Math. Math. Phys. \yr 2016 \vol 56 \issue 10 \pages 1813--1817 \crossref{https://doi.org/10.1134/S0965542516100080} \isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000386769200014} \scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84992380023}