An FPTAS for a vector subset search problem

DOI10.1134/S1990478914030041MaRDI QIDQ5264739zbMATH OpenOpenAlexFDO

Authors S. M. Romanchenko, A. V. Kel'manov

Publication date 27 July 2015

Published in Journal of Applied and Industrial Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

NP-hardnessEuclidean spaceapproximation schememinimum of the sum of squared distancesfinding a vector subsetfully polynomial time

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• An approximation scheme for a problem of search for a vector subset
• An approximation algorithm for solving the problem of the search of a subset of vectors
• An approximation scheme for the problem of finding a subsequence
• A 2-approximate algorithm to solve one problem of the family of disjoint vector subsets
• Pseudopolynomial algorithms for certain computationally hard vector subset and cluster analysis problems

Cites work

• scientific article; zbMATH DE number 3584897 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 3340881 (Why is no real title available?)
• An approximation algorithm for solving the problem of the search of a subset of vectors
• An approximation scheme for a problem of search for a vector subset
• Cluster Analysis and Mathematical Programming
• NP-completeness of some problems of a vectors subset choice
• NP-hardness of Euclidean sum-of-squares clustering
• Pseudopolynomial algorithms for certain computationally hard vector subset and cluster analysis problems
• The elements of statistical learning. Data mining, inference, and prediction

Cited in

(16)

• Easy NP-hardness Proofs of Some Subset Choice Problems
• An approximation algorithm for a problem of partitioning a sequence into clusters with constraints on their cardinalities
• Polynomial-time approximation algorithm for the problem of cardinality-weighted variance-based 2-clustering with a given center
• Approximation scheme for the problem of weighted 2-clustering with a fixed center of one cluster
• An approximation scheme for the problem of finding a subsequence
• Fully polynomial-time approximation scheme for a special case of a quadratic Euclidean 2-clustering problem
• An approximation scheme for a problem of search for a vector subset
• A 2-approximate algorithm to solve one problem of the family of disjoint vector subsets
• Selecting a subset of diverse points based on the squared Euclidean distance
• A fully polynomial-time approximation scheme for a sequence 2-cluster partitioning problem
• Exact pseudo-polynomial algorithms for a balanced 2-clustering problem
• 2-Approximation Polynomial-Time Algorithm for a Cardinality-Weighted 2-Partitioning Problem of a Sequence
• Approximation algorithm for the problem of partitioning a sequence into clusters
• Exact algorithms for two integer-valued problems of searching for the largest subset and longest subsequence
• Solving some vector subset problems by Voronoi diagrams
• Randomized algorithms for some hard-to-solve problems of clustering a finite set of points in Euclidean space

This page was built for publication: An FPTAS for a vector subset search problem

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