Much progress has been made on problems involving optimization of submodular functions under various constraints. However, the resulting algorithms, in particular the ones based on the "multilinear relaxation", are often quite slow. In this talk, I will discuss some recent efforts on making these algorithms faster and more practical. We design near-linear and near-quadratic algorithms for maximization of submodular functions under several common constraints. The techniques that we use include ground set sparsification, a coarse variant of the continuous greedy algorithm, and multiplicative weight updates. Some of the new algorithms have been implemented and showed improvements on instances arising in active set selection for nonparametric learning and exemplar-based clustering. Based on recent works with (1) C. Chekuri and T.S. Jayram (2) B. Mirzasoleiman, A. Badanidiyuru, A. Karbasi and A. Krause