An FPTAS for a vector subset search problem
DOI10.1134/S1990478914030041zbMATH Open1324.68245OpenAlexW1969181306MaRDI QIDQ5264739FDOQ5264739
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
NP-hardnessEuclidean spaceapproximation schememinimum of the sum of squared distancesfinding a vector subsetfully polynomial time
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Cites Work
- The elements of statistical learning. Data mining, inference, and prediction
- NP-hardness of Euclidean sum-of-squares clustering
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Cluster Analysis and Mathematical Programming
- Title not available (Why is that?)
- Title not available (Why is that?)
- Pseudopolynomial algorithms for certain computationally hard vector subset and cluster analysis problems
- An approximation scheme for a problem of search for a vector subset
- Title not available (Why is that?)
Cited In (13)
- 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
- 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
- Selecting a subset of diverse points based on the squared Euclidean distance
- 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
- Exact pseudopolynomial algorithms for a balanced 2-clustering problem
- Easy NP-hardness Proofs of Some Subset Choice Problems
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)
