Differentially Private Hierarchical Clustering with Provable Approximation Guarantees.
Jacob ImolaAlessandro EpastoMohammad MahdianVincent Cohen-AddadVahab MirrokniPublished in: ICML (2023)
Keyphrases
- approximation guarantees
- hierarchical clustering
- differentially private
- greedy algorithm
- approximation algorithms
- lower bound
- np hard
- differential privacy
- objective function
- clustering method
- approximation ratio
- linear programming relaxation
- constant factor
- single linkage
- worst case
- greedy algorithms
- k means
- partitional clustering
- privacy preserving
- special case
- data sets
- hierarchical clustering methods
- hierarchical clustering algorithm
- knapsack problem
- upper bound
- clustering algorithm
- privacy preservation
- dynamic programming
- training data
- web pages