Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

01.10.2019 | MATHEMATICAL THEORY OF PATTERN RECOGNITION | Ausgabe 4/2019

Pattern Recognition and Image Analysis 4/2019

An Accelerated Exact Algorithm for the One-Dimensional M-Variance Problem

Zeitschrift:
Pattern Recognition and Image Analysis > Ausgabe 4/2019
Autoren:
A. V. Kel’manov, P. S. Ruzankin
Wichtige Hinweise
https://static-content.springer.com/image/art%3A10.1134%2FS1054661819040072/MediaObjects/11493_2019_6024_Fig1_HTML.gif
Aleksandr Vasil’evich Kel’manov. Born 1952. Graduated from Izhevsk State Technical University in 1974 with specialty in Applied Mathematics. Received Candidate’s Degree in Engineering Cybernetics and Information Theory in 1980 and Doctor of Sciences degree in Physics and Mathematics in 1994. Currently with the Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, head of Data Analysis Laboratory. Scientific interests: discrete optimization, NP-hard problems, efficient algorithms with performance guarantees, data analysis, data mining, pattern recognition, clustering. Author of more than 200 publications.
https://static-content.springer.com/image/art%3A10.1134%2FS1054661819040072/MediaObjects/11493_2019_6024_Fig2_HTML.gif
Pavel Sergeevich Ruzankin. Born 1974. Graduated from Novosibirsk State University in 1999 with specialty in Mathematics. Received Candidate’s Degree in Mathematics in 2001. Currently with the Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Senior Research Scientist in Theory of Probability and Mathematical Statistics Laboratory. Scientific interests: medical statistics, poisson approximation, small deviations. Author of more than 20 publications.
Translated by A. Muravnik

Abstract

The known quadratic \(NP\)-hard (in the strong sense) \(M\)-variance problem is considered. It arises in the following typical problem of data analysis: in a set of \(N\) objects determined by their characteristics (features), find a subset of \(M\) elements close to each other. For the one-dimensional case, an accelerated exact algorithm with complexity \(\mathcal{O}(N{\kern 1pt} \log{\kern 1pt} N)\) is proposed.

Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 69.000 Bücher
  • über 500 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 50.000 Bücher
  • über 380 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Maschinenbau + Werkstoffe




Testen Sie jetzt 30 Tage kostenlos.

Literatur
Über diesen Artikel

Weitere Artikel der Ausgabe 4/2019

Pattern Recognition and Image Analysis 4/2019 Zur Ausgabe

ARTIFICIAL INTELLIGENCE TECHNIQUES IN PATTERN RECOGNITION AND IMAGE ANALYSIS

Estimation of the Closeness to a Semantic Pattern of a Topical Text without Construction of Periphrases

Premium Partner

    Bildnachweise