An FPTAS for a vector subset search problem

DOI10.1134/S1990478914030041zbMath1324.68245OpenAlexW1969181306MaRDI QIDQ5264739

S. M. Romanchenko, Alexander 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

Euclidean spaceNP-hardnessapproximation 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)

Related Items (13)

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 ⋮ Approximation algorithm for the problem of partitioning a sequence into clusters ⋮ Approximation scheme for the problem of weighted 2-clustering with a fixed center of one cluster ⋮ Exact pseudopolynomial algorithms for a balanced 2-clustering problem ⋮ Solving some vector subset problems by Voronoi diagrams ⋮ 2-Approximation Polynomial-Time Algorithm for a Cardinality-Weighted 2-Partitioning Problem of a Sequence ⋮ 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 ⋮ Exact algorithms for two integer-valued problems of searching for the largest subset and longest subsequence ⋮ Easy NP-hardness Proofs of Some Subset Choice Problems ⋮ Randomized algorithms for some hard-to-solve problems of clustering a finite set of points in Euclidean space

Cites Work

• NP-hardness of Euclidean sum-of-squares clustering
• Pseudopolynomial algorithms for certain computationally hard vector subset and cluster analysis problems
• An approximation scheme for a problem of search for a vector subset
• Cluster Analysis and Mathematical Programming
• The elements of statistical learning. Data mining, inference, and prediction
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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