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






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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
Received: 20.11.2015

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}


Linking options:
  • http://mi.mathnet.ru/eng/zvmmf10476
  • http://mi.mathnet.ru/eng/zvmmf/v56/i10/p1831

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Журнал вычислительной математики и математической физики Computational Mathematics and Mathematical Physics
    Number of views:
    This page:131
    Full text:12
    References:30
    First page:10

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2021