EFFICIENT APPROXIMATION ALGORITHMS FOR PAIRWISE DATA CLUSTERING AND APPLICATIONS

DOI10.1142/S0218195904001378MaRDI QIDQ4818598zbMATH OpenOpenAlexFDO

Authors Danny Z. Chen, J. J. Mason, Steven R. Schmid, Xiaodong Wu

Publication date 29 September 2004

Published in International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0218195904001378

zbMATH Keywords

approximation algorithmssparsest cutsminimum normalized cutspairwise data clustering

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• Pairwise data clustering and applications
• Approximation algorithms for min-sum \(p\)-clustering
• Clustering to minimize the maximum intercluster distance
• Graph Clustering and Minimum Cut Trees
• Approximation algorithms for clustering to minimize the sum of diameters

Cites work

• scientific article; zbMATH DE number 3800811 (Why is no real title available?)
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• Fast Approximate Graph Partitioning Algorithms
• Fast approximation algorithms for multicommodity flow problems
• Introduction to algorithms
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• The maximum concurrent flow problem

Cited in

(11)

• A polynomial algorithm for balanced clustering via graph partitioning
• scientific article; zbMATH DE number 1303609 (Why is no real title available?)
• Pairwise data clustering and applications
• Shift of pairwise similarities for data clustering
• Annealing and the normalized N-cut
• On the complexity of isoperimetric problems on trees
• An approximate distribution for the normalized cut
• scientific article; zbMATH DE number 1844606 (Why is no real title available?)
• Mean isoperimetry with control on outliers: exact and approximation algorithms
• A polynomial time algorithm for Rayleigh ratio on discrete variables: replacing spectral techniques for expander ratio, normalized cut, and Cheeger constant
• Normalized cuts are approximately inverse exit times

This page was built for publication: EFFICIENT APPROXIMATION ALGORITHMS FOR PAIRWISE DATA CLUSTERING AND APPLICATIONS

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