Attainable accuracy guarantee for the k-medians clustering in [0, 1]

DOI10.1007/S11590-018-1305-3MaRDI QIDQ2010139zbMATH OpenOpenAlexFDO

Authors Daniel Khachay, M. Yu. Khachaĭ

Publication date 3 December 2019

Published in Optimization Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11590-018-1305-3

zbMATH Keywords

\(k\)-medians clusteringattainable accuracyFarkas-Minkowski lemmazero-sum two-player game

Mathematics Subject Classification ID

Case-oriented studies in operations research (90B90) 2-person games (91A05) Applications of game theory (91A80)

Review text

In an original scientific manner, the authors contribute to the study of the renowned \(k\)-medians clustering problem in [0,1], following the attainable appropriate accuracy and the well known Farkas-Minkowski lemma.

Recommendations

• Approximation Algorithms for Aversion k-Clustering via Local k-Median
• Optimal time bounds for approximate clustering
• A \(k\)-median algorithm with running time independent of data size
• Smaller coresets for \(k\)-median and \(k\)-means clustering
• Clustering for metric and nonmetric distance measures

Cites work

• Algorithmic aspects of pyramidal tours with restricted jump-backs
• Bisecting K-means and 1D projection divisive clustering: a unified framework and experimental comparison
• Enhancing principal direction divisive clustering
• Fine-grained complexity analysis of two classic TSP variants
• Generalized pyramidal tours for the generalized traveling salesman problem
• Guaranteed clustering and biclustering via semidefinite programming
• scientific article; zbMATH DE number 2089373 (Why is no real title available?)
• scientific article; zbMATH DE number 1234104 (Why is no real title available?)
• scientific article; zbMATH DE number 2079382 (Why is no real title available?)
• Linear-time approximation schemes for clustering problems in any dimensions
• On coresets for k-means and k-median clustering
• One-dimensional center-based l 1-clustering method
• Pattern classification.
• Pyramidal tours with step-backs and the asymmetric traveling salesman problem
• Robust principal component analysis?
• The traveling salesman problem and its variations.

Cited in

(2)

• On decompositions of decision function quality measure
• Approximation Algorithms for Aversion k-Clustering via Local k-Median

This page was built for publication: Attainable accuracy guarantee for the \(k\)-medians clustering in [0, 1]

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