General information
Latest issue
Impact factor

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Diskretn. Anal. Issled. Oper.:

Personal entry:
Save password
Forgotten password?

Diskretn. Anal. Issled. Oper., 2014, Volume 21, Number 3, Pages 41–52 (Mi da774)  

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

FPTAS for solving a problem of search for a vector subset

A. V. Kel'manovab, S. M. Romanchenkoab

a S. L. Sobolev Institute of Mathematics, SB RAS, 4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
b Novosibirsk State University, 2 Pirogov St., 630090 Novosibirsk, Russia

Abstract: We consider one NP-hard problem of searching for a vector subset in a given finite Euclidean vector set. It is assumed that the desired subset has a fixed cardinality and contains vectors close to the subset center under the criterion of the minimum sum-of-squared distances. The subset center is defined as the mean value of elements of required subsets. We prove that (unless P$=$NP) there are no fully polynomial time approximation scheme (FPTAS) for the general case of the problem. FPTAS for the case of fixed space dimension is presented. Bibliogr. 12.

Keywords: search for a vector subset, Euclidean space, minimum sum-of-squared distances, NP-hardness, FPTAS.

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

English version:
Journal of Applied and Industrial Mathematics, 2014, 8:3, 329–336

Bibliographic databases:

UDC: 519.16+519.85
Received: 11.11.2013
Revised: 29.01.2014

Citation: A. V. Kel'manov, S. M. Romanchenko, “FPTAS for solving a problem of search for a vector subset”, Diskretn. Anal. Issled. Oper., 21:3 (2014), 41–52; J. Appl. Industr. Math., 8:3 (2014), 329–336

Citation in format AMSBIB
\by A.~V.~Kel'manov, S.~M.~Romanchenko
\paper FPTAS for solving a~problem of search for a~vector subset
\jour Diskretn. Anal. Issled. Oper.
\yr 2014
\vol 21
\issue 3
\pages 41--52
\jour J. Appl. Industr. Math.
\yr 2014
\vol 8
\issue 3
\pages 329--336

Linking options:

    SHARE: FaceBook Twitter Livejournal

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

    This publication is cited in the following articles:
    1. Zverkov O.A., Seliverstov A.V., Lyubetsky V.A., “a Database of Plastid Protein Families From Red Algae and Apicomplexa and Expression Regulation of the Moeb Gene”, Biomed Res. Int., 2015, 510598  crossref  isi  scopus
    2. A. V. Kel'manov, V. I. Khandeev, “Fully polynomial-time approximation scheme for a special case of a quadratic Euclidean 2-clustering problem”, Comput. Math. Math. Phys., 56:2 (2016), 334–341  mathnet  crossref  crossref  isi  elib
    3. 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  mathnet  crossref  crossref  mathscinet  elib
    4. A. V. Kel'manov, L. V. Mikhailova, S. A. Khamidullin, V. I. Khandeev, “An approximation algorithm for the problem of partitioning a sequence into clusters with constraints on their cardinalities”, Proc. Steklov Inst. Math. (Suppl.), 299, suppl. 1 (2017), 88–96  mathnet  crossref  crossref  mathscinet  isi  elib
    5. 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  mathnet  crossref  crossref  mathscinet  elib
    6. V. V. Shenmaier, “Solving some vector subset problems by Voronoi diagrams”, J. Appl. Industr. Math., 10:4 (2016), 560–566  mathnet  crossref  crossref  mathscinet  elib
    7. A. E. Galashov, A. V. Kel'manov, “On pseudopolynomial-time solvability of a quadratic Euclidean problem of finding a family of disjoint subsets”, Num. Anal. Appl., 10:1 (2017), 11–16  mathnet  crossref  crossref  mathscinet  isi  elib
    8. 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  mathnet  crossref  crossref  isi  elib
    9. A. V. Kelmanov, S. M. Romanchenko, S. A. Khamidullin, “An approximation scheme for a problem of finding a subsequence”, Num. Anal. Appl., 10:4 (2017), 313–323  mathnet  crossref  crossref  isi  elib
    10. A. V. Kel'manov, L. V. Mikhailova, S. A. Khamidullin, V. I. Khandeev, “Approximation algorithm for the problem of partitioning a sequence into clusters”, Comput. Math. Math. Phys., 57:8 (2017), 1376–1383  mathnet  crossref  crossref  isi  elib
    11. A. Ageev, A. Kel'manov, A. Pyatkin, S. Khamidullin, V. Shenmaier, “1/2-approximation polynomial-time algorithm for a problem of searching a subset”, 2017 International Multi-Conference on Engineering, Computer and Information Sciences (SIBIRCON), IEEE, 2017, 8–12  crossref  isi
    12. A. Kel'manov, “Efficient approximation algorithms for some NP-hard problems of partitioning a set and a sequence”, 2017 International Multi-Conference on Engineering, Computer and Information Sciences (SIBIRCON), IEEE, 2017, 87–90  crossref  isi
    13. A. Kel'manov, A. Motkova, “An approximation polynomial-time algorithm for a cardinality-weighted 2-clustering problem”, 2017 International Multi-Conference on Engineering, Computer and Information Sciences (SIBIRCON), IEEE, 2017, 94–96  crossref  isi
    14. A. V. Kel'manov, A. V. Motkova, “Polynomial-time approximation algorithm for the problem of cardinality-weighted variance-based 2-clustering with a given center”, Comput. Math. Math. Phys., 58:1 (2018), 130–136  mathnet  crossref  crossref  isi  elib
    15. A. Kel'manov, A. Motkova, V. Shenmaier, “An approximation scheme for a weighted two-cluster partition problem”, Analysis of Images, Social Networks and Texts, AIST 2017, Lecture Notes in Computer Science, 10716, eds. W. van der Aalst, D. Ignatov, M. Khachay, S. Kuznetsov, V. Lempitsky, I. Lomazova, N. Loukachevitch, A. Napoli, A. Panchenko, P. Pardalos, A. Savchenko, S. Wasserman, Springer, 2018, 323–333  crossref  isi  scopus
  • Дискретный анализ и исследование операций
    Number of views:
    This page:291
    Full text:79
    First page:32

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