E. Kh. Gimadi, Yu. V. Glazkov, I. A. Rykov, “The vector subset problem with integer coordinates in Euclidean space with the maximum sum”, Diskretn. Anal. Issled. Oper., 15:4 (2008), 30–43; J. Appl. Industr. Math., 3:3 (2009), 343

Diskretnyi Analiz i Issledovanie Operatsii

RUS ENG

JOURNALS PEOPLE ORGANISATIONS CONFERENCES SEMINARS VIDEO LIBRARY PACKAGE AMSBIB

JavaScript is disabled in your browser. Please switch it on to enable full functionality of the website

	General information
	Latest issue
	Archive
	Impact factor
	Guidelines for authors

	Search papers
	Search references

	RSS
	Latest issue
	Current issues
	Archive issues
	What is RSS

Diskretn. Anal. Issled. Oper.:
Year:
Volume:
Issue:
Page:
	Find

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

Diskretnyi Analiz i Issledovanie Operatsii, 2008, Volume 15, Issue 4, Pages 30–43 (Mi da539)

This article is cited in 13 scientific papers (total in 13 papers)

The vector subset problem with integer coordinates in Euclidean space with the maximum sum

E. Kh. Gimadi, Yu. V. Glazkov, I. A. Rykov

Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences

Full-text PDF (265 kB) Citations (13)

References:

PDF

HTML

Abstract: Two problems of selecting a subset of $m$ vectors with the maximum norm of sum from a set of $n$ vectors in Euclidean space $\mathbb R^k$ is considered. It is supposed that the coordinates of the vectors are integer. Using the dynamic programming technique new optimal algorithms are constructed. They have pseudopolynomial complexity, when the dimension $k$ of the vector space is fixed. New algorithms have certain advantages (with respect to earlier known algorithms): the vector subset problem can be solved faster, if $m<(k/2)^k$, and the time complexity is $k^{k-1}$ times less for the problem with an additional restriction on the order of vectors independently of $m$. Bibl. 5.

Keywords: subset selection, Euclidian metric, time complexity, pseudopolynomial algorithm, dynamic programming.

Received: 16.03.2008
Revised: 20.06.2008

English version:
Journal of Applied and Industrial Mathematics, 2009, Volume 3, Issue 3, Pages 343–352
DOI: https://doi.org/10.1134/S1990478909030041

Bibliographic databases:

UDC: 519.8

Language: Russian

Citation: E. Kh. Gimadi, Yu. V. Glazkov, I. A. Rykov, “The vector subset problem with integer coordinates in Euclidean space with the maximum sum”, Diskretn. Anal. Issled. Oper., 15:4 (2008), 30–43; J. Appl. Industr. Math., 3:3 (2009), 343–352

Citation in format AMSBIB

\Bibitem{GimGlaRyk08}

\by E.~Kh.~Gimadi, Yu.~V.~Glazkov, I.~A.~Rykov

\paper The vector subset problem with integer coordinates in Euclidean space with the maximum sum

\jour Diskretn. Anal. Issled. Oper.

\yr 2008

\vol 15

\issue 4

\pages 30--43

\mathnet{http://mi.mathnet.ru/da539}

\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=2543598}

\zmath{https://zbmath.org/?q=an:1249.90171}

\transl

\jour J. Appl. Industr. Math.

\yr 2009

\vol 3

\issue 3

\pages 343--352

\crossref{https://doi.org/10.1134/S1990478909030041}

\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-70349150916}

Linking options:

https://www.mathnet.ru/eng/da539

https://www.mathnet.ru/eng/da/v15/i4/p30

This publication is cited in the following 13 articles:

A. V. Kel'manov, A. V. Motkova, V. V. Shenmaier, “Approximation scheme for the problem of weighted 2-partitioning with a fixed center of one cluster”, Proc. Steklov Inst. Math. (Suppl.), 303, suppl. 1 (2018), 136–145
V. V. Shenmaier, “An exact algorithm for finding a vector subset with the longest sum”, J. Appl. Industr. Math., 11:4 (2017), 584–593
Kel'manov A. Khandeev V., “Some Algorithms With Guaranteed Accuracy For 2-Clustering Problems With Given Center of One Cluster”, 2017 International Multi-Conference on Engineering, Computer and Information Sciences (SIBIRCON), IEEE, 2017, 91–93
Eremeev A.V. Kel'manov A.V. Pyatkin A.V., “On Complexity of Searching a Subset of Vectors With Shortest Average Under a Cardinality Restriction”, Analysis of Images, Social Networks and Texts, AIST 2016, Communications in Computer and Information Science, 661, ed. Ignatov D. Khachay M. Labunets V. Loukachevitch N. Nikolenko S. Panchenko A. Savchenko A. Vorontsov K., Springer International Publishing Ag, 2017, 51–57
A. V. Kel'manov, S. A. Khamidullin, V. I. Khandeev, “Fully polynomial-time approximation scheme for a sequence $2$-clustering problem”, J. Appl. Industr. Math., 10:2 (2016), 209–219
A. V. Kel'manov, A. V. Motkova, “Exact pseudopolinomial algorithms for a balanced $2$-clustering problem”, J. Appl. Industr. Math., 10:3 (2016), 349–355
A. V. Eremeev, A. V. Kel'manov, A. V. Pyatkin, “On the complexity and approximability of some Euclidean optimal summing problems”, Comput. Math. Math. Phys., 56:10 (2016), 1813–1817
Edward Gimadi, Ivan Rykov, Lecture Notes in Computer Science, 9869, Discrete Optimization and Operations Research, 2016, 148
A. V. Eremeev, A. V. Kel'manov, A. V. Pyatkin, “On the complexity of some Euclidean optimal summing problems”, Dokl. Math., 93:3 (2016), 286
A. V. Kel'manov, V. I. Khandeev, “An exact pseudopolynomial algorithm for a bi-partitioning problem”, J. Appl. Industr. Math., 9:4 (2015), 497–502
A. V. Dolgushev, A. V. Kel'manov, V. V. Shenmaier, “Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters”, Proc. Steklov Inst. Math. (Suppl.), 295, suppl. 1 (2016), 47–56
A. V. Dolgushev, A. V. Kel'manov, “An approximation algorithm for one problem of cluster analysis”, J. Appl. Industr. Math., 5:4 (2011), 551–558
E. Kh. Gimadi, A. V. Pyatkin, I. A. Rykov, “On polynomial solvability of some vector subset problems in Euclidean space with fixed dimension”, J. Appl. Industr. Math., 4:1 (2010), 48–53

Citing articles in Google Scholar: Russian citations, English citations
Related articles in Google Scholar: Russian articles, English articles

Дискретный анализ и исследование операций

Statistics & downloads:
Abstract page:	694
Full-text PDF :	162
References:	97
First page:	11

Registration to the website

Logotypes