Polynomial-time approximation algorithm for the problem of cardinality-weighted variance-based 2-clustering with a given center

DOI10.1134/S0965542518010074zbMath1478.68450OpenAlexW2793344488WikidataQ130166335 ScholiaQ130166335MaRDI QIDQ1746358

A. V. Motkova, Alexander Kel'Manov

Publication date: 25 April 2018

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

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

zbMATH Keywords

Euclidean spaceNP-hardnesspolynomial-time 2-approximation algorithmweighted 2-clustering

Mathematics Subject Classification ID

Applications of mathematical programming (90C90) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (4)

Exact algorithms of searching for the largest size cluster in two integer 2-clustering problems ⋮ 2-Approximation Polynomial-Time Algorithm for a Cardinality-Weighted 2-Partitioning Problem of a Sequence ⋮ Exact Algorithm for the One-Dimensional Quadratic Euclidean Cardinality-Weighted 2-Clustering with Given Center Problem ⋮ Randomized algorithms for some hard-to-solve problems of clustering a finite set of points in Euclidean space

Uses Software

• ElemStatLearn
• PRMLT

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• NP-hardness of some quadratic Euclidean 2-clustering problems
• NP-hardness of Euclidean sum-of-squares clustering
• A randomized approximation scheme for metric MAX-CUT
• A randomized algorithm for two-cluster partition of a set of vectors
• Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters
• Fully polynomial-time approximation scheme for a special case of a quadratic Euclidean 2-clustering problem
• On the complexity of some quadratic Euclidean 2-clustering problems
• Exact pseudopolynomial algorithms for a balanced 2-clustering problem
• A Fully Polynomial-Time Approximation Scheme for a Special Case of a Balanced 2-Clustering Problem
• An exact pseudopolynomial algorithm for a problem of the two-cluster partitioning of a set of vectors
• P-Complete Approximation Problems
• Data Mining
• A 2-approximation polynomial algorithm for a clustering problem
• An FPTAS for a vector subset search problem
• Cluster Analysis and Mathematical Programming
• The elements of statistical learning. Data mining, inference, and prediction

This page was built for publication: Polynomial-time approximation algorithm for the problem of cardinality-weighted variance-based 2-clustering with a given center