Sanjoy Dasgupta (Theory Seminar)

dasgupta.jpgTheory Seminar
"An approximation algorithm for hierarchical clustering"
Sanjoy Dasgupta
Tuesday, October 27th, 2015, 1:00pm
EBU3B, Room 4258

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.