Interesting Papers at SODA 2009 – Machine Learning (Theory)

Several talks seem potentially interesting to ML folks at this year’s SODA. Maria-Florina Balcan, Avrim Blum, and Anupam Gupta, Approximate Clustering without the Approximation. This paper gives reasonable algorithms with provable approximation guarantees for k-median and other notions of clustering. It’s conceptually interesting, because it’s the second example I’ve seen where NP hardness is subv