Clustering for metric and nonmetric distance measures

DOI10.1145/1824777.1824779zbMath1300.68050OpenAlexW2620598837MaRDI QIDQ2930341

Christian Sohler, Marcel R. Ackermann, Johannes Blömer

Publication date: 18 November 2014

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1824777.1824779

zbMATH Keywords

approximation algorithmKullback-Leibler divergencerandom samplingMahalanobis distanceBregman divergencesItakura-Saito divergence

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Measures of information, entropy (94A17) Approximation algorithms (68W25)

Related Items (18)

Minimization of Gini impurity: NP-completeness and approximation algorithm via connections with the \(k\)-means problem ⋮ Concentration of kernel matrices with application to kernel spectral clustering ⋮ A Pitman measure of similarity in k-means for clustering heavy-tailed data ⋮ A Lagrangian search method for the \(P\)-median problem ⋮ Approximating ( k,ℓ )-Median Clustering for Polygonal Curves ⋮ SEND: a novel dissimilarity metric using ensemble properties of the feature space for clustering numerical data ⋮ A family of pairwise multi-marginal optimal transports that define a generalized metric ⋮ Linear-time approximation scheme for \(k\)-means clustering of axis-parallel affine subspaces ⋮ Mathematical Programming Formulations and Algorithms for Discrete k-Median Clustering of Time-Series Data ⋮ Faster algorithms for the constrained \(k\)-means problem ⋮ Parameterized \(k\)-clustering: tractability island ⋮ Improved analysis of \(D^2\)-sampling based PTAS for \(k\)-means and other clustering problems ⋮ A simple \(D^2\)-sampling based PTAS for \(k\)-means and other clustering problems ⋮ A deterministic sublinear-time nonadaptive algorithm for metric 1-median selection ⋮ An improved Bregman \(k\)-means++ algorithm via local search ⋮ A unified framework for clustering constrained data without locality property ⋮ Probabilistic smallest enclosing ball in high dimensions via subgradient sampling ⋮ Improved local search algorithms for Bregman \(k\)-means and its variants

This page was built for publication: Clustering for metric and nonmetric distance measures