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

DOI10.1007/s11590-018-1305-3zbMath1432.91009OpenAlexW2887156225MaRDI QIDQ2010139

Daniel Khachay, Mikhail Yu. Khachay

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

Farkas-Minkowski lemma\(k\)-medians clusteringattainable accuracyzero-sum two-player game

Mathematics Subject Classification ID

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

Related Items (1)

On decompositions of decision function quality measure

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Guaranteed clustering and biclustering via semidefinite programming
• Enhancing principal direction divisive clustering
• Pyramidal tours with step-backs and the asymmetric traveling salesman problem
• Generalized pyramidal tours for the generalized traveling salesman problem
• One-dimensional center-based l 1-clustering method
• The traveling salesman problem and its variations.
• Algorithmic Aspects of Pyramidal Tours with Restricted Jump-Backs
• Robust principal component analysis?
• Linear-time approximation schemes for clustering problems in any dimensions
• On coresets for k-means and k-median clustering
• Fine-grained complexity analysis of two classic TSP variants
• Bisecting K-means and 1D projection divisive clustering: a unified framework and experimental comparison

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