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

DOI10.1007/S11590-018-1305-3zbMATH Open1432.91009OpenAlexW2887156225MaRDI QIDQ2010139FDOQ2010139

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

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

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)