Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Pattern Recognition and Image Analysis
Published in: Pattern Recognition and Image Analysis 4/2019

01-10-2019 | MATHEMATICAL THEORY OF PATTERN RECOGNITION

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

Authors: A. V. Kel’manov, P. S. Ruzankin

Published in: Pattern Recognition and Image Analysis | Issue 4/2019

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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.
next article Subjective Restoration of Mathematical Models for a Research Object, Its Measurements, and Measurement-Data Interpretation

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

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

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

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

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

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




Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

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




 

Jetzt Wissensvorsprung sichern!

inform now
Literature
1.
G. James, D. Witten, T. Hastie, and R. Tibshirani, An Introduction to Statistical Learning: With Application in R (Springer Science + Business Media, New York, 2013).
2.
J. W. Osborne, Best Practices in Data Cleaning: A Complete Guide to Everything You Need to Do before and after Collecting Your Data, 1st ed. (SAGE Publ., Los Angeles, 2013).CrossRef
3.
T. de Waal, J. Pannekoek, and S. Scholtus, Handbook of Statistical Data Editing and Imputation (Wiley, Hoboken, NJ, 2011).CrossRef
4.
A. Farcomeni and L. Greco, Robust Methods for Data Reduction (Chapman and Hall/CRC, Boca Raton, 2015).MATH
5.
C. C. Aggarwal, Data Mining: The Textbook (Springer Int. Publ., 2015).MATH
6.
C. M. Bishop, Pattern Recognition and Machine Learning (Springer Science + Business Media, New York, 2006).
7.
T. Hastie, R. Tibshirani, and J. Friedman, The Elements of Statistical Learning: Data Mining, Inference, and Prediction, 2nd ed. (Springer, New York, 2009).CrossRef
8.
I. Goodfellow, Y. Bengio, and A. Courville, Deep Learning, in Adaptive Computation and Machine Learning Series (MIT Press, Cambridge, MA, 2016).MATH
9.
A. Aggarwal, H. Imai, N. Katoh, and S. Suri, “Finding \(k\) points with minimum diameter and related problems,” J. Algorithms 12 (1), 38–56 (1991).MathSciNetCrossRef
10.
A. V. Kel’manov and A. V. Pyatkin, “NP-Completeness of some problems of choosing a vector subset,” J. Appl. Indust. Math. 5 (3), 352–357 (2011).CrossRef
11.
C. H. Papadimitriou, Computational Complexity (Addison-Wesley, New York, 1994).MATH
12.
M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979).MATH
13.
A. V. Kel’manov and S. M. Romanchenko, “An approximation algorithm for solving a problem of search for a vector subset,” J. Appl. Indust. Math. 6 (1), 90–96 (2012).CrossRef
14.
V. V. Shenmaier, “An approximation scheme for a problem of search for a vector subset,” J. Appl. Indust. Math. 6 (3), 381–386 (2012).MathSciNetCrossRef
15.
A. Kel’manov, V. Khandeev, and A. Panasenko, “Randomized algorithms for some clustering problems,” in Optimization Problems and Their Applications, OPTA 2018, Ed. by A. Eremeev, M. Khachay, Y. Kochetov, and P. Pardalos, Communications in Computer and Information Science (Springer, Cham, 2018), Vol. 871, pp. 109–119.
16.
A. V. Kel’manov and S. M. Romanchenko, “An FPTAS for a vector subset search problem,” J. Appl. Indust. Math. 8 (3), 329–336 (2014).CrossRef
17.
A. Kel’manov, A. Motkova, and V. Shenmaier, “An approximation scheme for a weighted two-cluster partition problem,” in Analysis of Images, Social Networks and Texts, AIST 2017, Ed. by W. M. P. van der Aalst, Lecture Notes in Computer Science (Springer, Cham, 2018), Vol. 10716, pp. 323–333.
18.
V. V. Shenmaier, “Solving some vector subset problems by Voronoi diagrams,” J. Appl. Indust. Math. 10 (4), 560–566 (2016).MathSciNetCrossRef
19.
A. V. Kel’manov and S. M. Romanchenko, “Pseudopolynomial algorithms for certain computationally hard vector subset and cluster analysis problems,” Autom. Remote Control 73 (2), 349–354 (2012).MathSciNetCrossRef
Metadata
Title
An Accelerated Exact Algorithm for the One-Dimensional M-Variance Problem
Authors
A. V. Kel’manov
P. S. Ruzankin
Publication date
01-10-2019
Publisher
Pleiades Publishing
Published in
Pattern Recognition and Image Analysis / Issue 4/2019
Print ISSN: 1054-6618
Electronic ISSN: 1555-6212
DOI
https://doi.org/10.1134/S1054661819040072

Other articles of this Issue 4/2019

Pattern Recognition and Image Analysis 4/2019 Go to the issue

APPLIED PROBLEMS

Surface Classification of Damaged Concrete Using Deep Convolutional Neural Network

APPLIED PROBLEMS

Segmentation and Feature Extraction of Endoscopic Images for Making Diagnosis of Acute Appendicitis

APPLIED ARTIFICIAL INTELLIGENCE SYSTEMS. KNOWLEDGE-BASED AND INTELLIGENCE SYSTEMS

On the Procedures of Generation of Numerical Features over Partitions of Sets of Objects in the Problem of Predicting Numerical Target Variables

APPLIED PROBLEMS

Estimation of Blood Flow Velocity in Coronary Arteries Based on the Movement of Radiopaque Agent

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

APPLIED PROBLEMS

A Method for Predicting Rare Events by Multidimensional Time Series with the Use of Collective Methods

Premium Partner

    Image Credits