Ashwinkumar Badanidiyuru

Lazier Than Lazy Greedy

2015

Is it possible to maximize a monotone submodular function faster than the widely used lazy greedy algorithm (also known as accelerated greedy), both in theory and practice? In this paper, we develop the first linear-time …