PTAS for p-means q-medoids r-given clustering problem

DOI10.1007/978-3-031-35305-5_9MaRDI QIDQ6134053zbMATH OpenOpenAlexFDO

Authors Artem Pyatkin

Publication date 21 August 2023

Published in Mathematical Optimization Theory and Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-031-35305-5_9

zbMATH Keywords

clustering\(k\)-meanscentroidPTASmedoid

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25)

Recommendations

• Quadratic Euclidean 1-mean and 1-median 2-clustering problem with constraints on the size of the clusters: complexity and approximability
• NP-hardness of quadratic Euclidean 1-mean and 1-median 2-clustering problem with constraints on the cluster sizes
• Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters
• The Problem K-Means and Given J-Centers: Polynomial Solvability in One Dimension
• On the complexity of some quadratic Euclidean 2-clustering problems

Cites work

• scientific article; zbMATH DE number 41467 (Why is no real title available?)
• scientific article; zbMATH DE number 3340881 (Why is no real title available?)
• A 2-approximation polynomial algorithm for a clustering problem
• A posteriori detection of a quasiperiodic fragment with a given number of repetitions in a numerical sequence
• An approximation scheme for a problem of search for a vector subset
• Faster Scaling Algorithms for Network Problems
• Grouping Multidimensional Data
• NP-hardness of Euclidean sum-of-squares clustering
• NP-hardness of quadratic Euclidean 1-mean and 1-median 2-clustering problem with constraints on the cluster sizes
• On Grouping for Maximum Homogeneity
• On the complexity of a search for a subset of ``similar vectors
• The problem of finding a subset of vectors with maximal total weight
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems

Cited in

(1)

• A randomized PTAS for the minimum consensus clustering with a fixed number of clusters

This page was built for publication: PTAS for \(p\)-means \(q\)-medoids \(r\)-given clustering problem

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