Pseudopolynomial algorithms for certain computationally hard vector subset and cluster analysis problems

DOI10.1134/S0005117912020129zbMath1307.68070OpenAlexW1970454533MaRDI QIDQ2261720

S. M. Romanchenko, Alexander Kel'Manov

Publication date: 13 March 2015

Published in: Automation and Remote Control (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (7)

Selecting a subset of diverse points based on the squared Euclidean distance ⋮ 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 ⋮ A 2-approximate algorithm to solve one problem of the family of disjoint vector subsets ⋮ Exact algorithms for two integer-valued problems of searching for the largest subset and longest subsequence ⋮ Randomized algorithms for some hard-to-solve problems of clustering a finite set of points in Euclidean space ⋮ An FPTAS for a vector subset search problem

Cites Work

• Evaluating a branch-and-bound RLT-based algorithm for minimum sum-of-squares clustering
• NP-hardness of Euclidean sum-of-squares clustering
• The Planar k-Means Problem is NP-Hard
• Cluster Analysis and Mathematical Programming
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Pseudopolynomial algorithms for certain computationally hard vector subset and cluster analysis problems