Skip to main content
SpringerLink
Log in

Complexity of certain problems of searching for subsets of vectors and cluster analysis

  • Published:
Computational Mathematics and Mathematical Physics Aims and scope Submit manuscript

Abstract

The discrete extremal problems to which certain problems of searching for subsets of vectors and cluster analysis are reduced are proved to be NP-complete.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. A. V. Kel’manov and S. A. Khamidullin, “Posterior Detection of a Given Number of Identical Subsequences in a Quasi-Periodic Sequence,” Zh. Vychisl. Mat. Mat. Fiz. 41, 807–820 (2001) [Comput. Math. Math. Phys. 41, 762–774 (2001)].

    MathSciNet  Google Scholar 

  2. A. V. Kel’manov and B. Jeon, “A Posteriori Joint Detection and Discrimination of Pulses in a Quasiperiodic Pulse Train,” IEEE Trans. Signal Processing 52(3), 1–12 (2004).

    Article  MathSciNet  Google Scholar 

  3. A. V. Kel’manov and L. V. Mikhailova, “Joint Detection of a Given Number of Reference Fragments in a Quasi-Periodic Sequence and Its Partition into Segments Containing Series of Identical Fragments,” Zh. Vychisl. Mat. Mat. Fiz. 46, 172–189 (2006) [Comput. Math. Math. Phys. 46, 165–181 (2006)].

    MATH  MathSciNet  Google Scholar 

  4. A. V. Kel’manov and L. V. Mikhailova, “A Posteriori Joint Detection of Reference Fragments in a Quasi-Periodic Sequence,” Zh. Vychisl. Mat. Mat. Fiz. 48, 899–915 (2008) [Comput. Math. Math. Phys. 48, 850–865 (2008)].

    MATH  MathSciNet  Google Scholar 

  5. A. V. Kel’manov, L. V. Mikhailova, and S. A. Khamidullin, “A Posteriori Joint Detection of a Recurring Tuple of Reference Fragments in a Quasi-Periodic Sequence,” Zh. Vychisl. Mat. Mat. Fiz. 48, 168–184 (2008) [Comput. Math. Math. Phys. 48, 2276–2288 (2008)].

    MathSciNet  Google Scholar 

  6. A. V. Kel’manov, “Polynomial-Time Solvable NP-Hard Variants of Optimal Detection of a Recurring Fragment in a Numerical Sequence,” in Proceedings of Russian Conference on Discrete Optimization and Operations Research, Vladivostok, September 7–14, 2007 (Inst. Mat. Sib. Otd. Ross. Akad. Nauk, Novosibirsk, 2007).

    Google Scholar 

  7. A. V. Kel’manov, “Off-Line Detection of a Recurring Fragment in a Numerical Sequence,” Tr. Inst. Mekh. Mat. Ural. Otd. Ross. Akad. Nauk (Yekaterinburg) 14(2), 81–88 (2008).

    MathSciNet  Google Scholar 

  8. E. Kh. Gimadi, A. V. Kel’manov, M. A. Kel’manova, and S. A. Khamidullin, “A Posteriori Detection of a QuasiPeriodic Fragment in Numerical Sequences with Given Number of Recurrences,” Sib. Zh. Ind. Mat. 9(1(25)), 55–74 (2006).

    MathSciNet  Google Scholar 

  9. A. E. Baburin, E. Kh. Gimadi, N. I. Glebov, and A. V. Pyatkin, “The Problem of Finding a Subset of Vectors with the Maximum Total Weight,” Diskret. Anal. Issled. Operatsii, Ser. 2 14(1), 32–42 (2007).

    MathSciNet  Google Scholar 

  10. A. V. Kel’manov and A. V. Pyatkin, “On the Complexity of a Search for a Subset of “Similar” Vectors,” Dokl. Akad. Nauk 421, 590–592 (2008) [Dokl. Math. 78, 574–575 (2008)].

    MathSciNet  Google Scholar 

  11. A. V. Kel’manov and A. V. Pyatkin, “On a Variant of Search for a Subset of Vectors,” Diskret. Anal. Issled. Operatsii 15(5), 25–40 (2008).

    MathSciNet  Google Scholar 

  12. M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, CA, 1979).

    MATH  Google Scholar 

  13. P. Drineas, A. Frieze, R. Kannan, and V. Vinay, “Clustering Large Graphs via the Singular Value Decomposition,” Machine Learning 56, 9–33 (2004).

    Article  MATH  Google Scholar 

  14. D. Aloise and P. Hansen, “On the Complexity of Minimum Sum-of-Squares Clustering,” Les Cahiers du GERAD, G-2007-50 (2007).

  15. D. Aloise, A. Deshpande, P. Hansen, and P. Popat, “NP-Hardness of Euclidean Sum-of-Squares Clustering,” Les Cahiers du GERAD, G-2008-33 (2008).

  16. http://math.nsc.ru/~serge/qpsl/

Download references

Author information

Authors and Affiliations

  1. Sobolev Institute of Mathematics, Siberian Branch, Russian Academy of Sciences, pr. Akademika Koptyuga 4, Novosibirsk, 630090, Russia

    A. V. Kel’manov & A. V. Pyatkin

Authors
  1. A. V. Kel’manov
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. A. V. Pyatkin
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to A. V. Kel’manov.

Additional information

Original Russian Text © A.V. Kel’manov, A.V. Pyatkin, 2009, published in Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki, 2009, Vol. 49, No. 11, pp. 2059–2067.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Kel’manov, A.V., Pyatkin, A.V. Complexity of certain problems of searching for subsets of vectors and cluster analysis. Comput. Math. and Math. Phys. 49, 1966–1971 (2009). https://doi.org/10.1134/S0965542509110128

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1134/S0965542509110128

Key words

Search

Navigation