  The greedy strategy is an approximation algorithm to solve optimization
problems arising in decision making with multiple actions. How good is the
greedy strategy compared to the optimal solution? In this survey, we mainly
consider two classes of optimization problems where the objective function is
submodular. The first is set submodular optimization, which is to choose a set
of actions to optimize a set submodular objective function, and the second is
string submodular optimization, which is to choose an ordered set of actions to
optimize a string submodular function. Our emphasis here is on performance
bounds for the greedy strategy in submodular optimization problems.
Specifically, we review performance bounds for the greedy strategy, more
general and improved bounds in terms of curvature, performance bounds for the
batched greedy strategy, and performance bounds for Nash equilibria.
