Subset Selection Problems – Part 1


August 18, 2015


Amit Deshpande


Subset selection problem means finding a small subset of given data that maximizes diversity or information content or some other submodular function depending on the context. This definition can be suitably modified in each context, and has a wide range of interesting applications like feature selection, sensor placement, document summarization, diversification of search. I’ll review different theoretical attempts to capture this notion, the algorithmic ideas, practical applications, and their impact in return on basic research in graph theory, linear algebra, probability.