Submodular Maximization Under A Matroid Constraint: Asking more from an old friend, the Greedy Algorithm

Nived Rajaraman, Rahul Vaze

The classical problem of maximizing a submodular function under a matroid constraint is considered. Defining a new measure for the increments made by the greedy algorithm at each s…