Theory Seminar
"An approximation algorithm for hierarchical clustering"
Sanjoy Dasgupta
(UCSD)
Tuesday, October 27th, 2015, 1:00pm
EBU3B, Room 4258
Abstract:
The development of algorithms for hierarchical clustering has been hampered by a shortage of precise objective functions. To help address this situation, we introduce a simple cost function on hierarchies over a set of points, given pairwise similarities between those points. We show that this criterion behaves sensibly in canonical instances and that it admits a top-down construction procedure with a provably good approximation ratio.