On the complexity of some data analysis problems

DOI10.1134/S0965542510110163MaRDI QIDQ2996037zbMATH OpenOpenAlexFDO

Authors A. V. Kel'manov

Publication date 4 May 2011

Published in Computational Mathematics and Mathematical Physics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1134/s0965542510110163

zbMATH Keywords

data analysiscomplexityNP-completenessdiscrete optimization problemfinding subsets of vectors in the Euclidean space

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Estimation and detection in stochastic control theory (93E10) Sampling theory in information and communication theory (94A20)

Recommendations

• NP-completeness of some problems of a vectors subset choice
• On complexity of some problems of cluster analysis of vector sequences
• Computational complexity of two problems of cognitive data analysis
• On the complexity of certain problems of choosing subset of vectors
• Pseudopolynomial algorithms for certain computationally hard vector subset and cluster analysis problems

Cited in

(21)

• On the complexity of data disjunctions.
• scientific article; zbMATH DE number 1440100 (Why is no real title available?)
• Computing and Combinatorics
• A randomized algorithm for two-cluster partition of a set of vectors
• Exact and approximate discrete optimization algorithms for finding useful disjunctions of categorical predicates in data analysis
• NP-hardness of some data cleaning problem
• A family of NP-complete data aggregation problems
• NP-completeness of some problems of a vectors subset choice
• Computational complexity of two problems of cognitive data analysis
• Computational complexity and feasibility of data processing and interval computations
• Fully polynomial-time approximation scheme for a special case of a quadratic Euclidean 2-clustering problem
• A fully polynomial-time approximation scheme for a sequence 2-cluster partitioning problem
• An exact pseudopolynomial algorithm for a problem of the two-cluster partitioning of a set of vectors
• Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters
• NP-hardness of some quadratic Euclidean 2-clustering problems
• On the complexity of a search for a subset of ``similar vectors
• A parameterized complexity analysis of combinatorial feature selection problems
• Phage typing sets
• Challenges in statistical theory: complex data structures and algorithmic optimization. Abstracts from the workshop held August 23rd -- August 29th, 2009
• On the complexity of some quadratic Euclidean 2-clustering problems
• Data-reducing principal component analysis (PCA) is NP-hard even under the simplest interval uncertainty

This page was built for publication: On the complexity of some data analysis problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2996037)