Why is optimisation of submodular functions particularly interesting? Google Scholar suggests there were around 6000 articles on 'submodular' functions and optimisation 2000-2010, and 12,000 since 2010.
So my question, having bumped into a few of these articles, is, why is this topic particularly of interest now? What are the main problems where approaching a function as being submodular gets us something?
My woefully incomplete reading on the topic hasn't furnished me with good motivating examples!
 A: Many observation selection problems satisfy an intuitive diminishing returns property: adding an observation helps more if we made few observations so far and helps less if we already made a lot of observations. This concept is formalized by the property of submodularity. A set function $f:2^{V}\rightarrow \mathbb{R}$ is submodular iff for all $A\subseteq B\subseteq V$ and $s\in V\setminus B$ it holds that:
\begin{equation}
F(A\cup \{s\}) - F(A) \geq F(B\cup\{s\})-F(B)
\end{equation}
It can be shown that entropy and mutual information are submodular, which leads to a variety of interesting greedy optimization algorithms. We are interested in solving problems of the form:
\begin{equation}
    \max_{s\subseteq V} f(S)
\end{equation}
subject to constraints on $S$. Two such constraints: a cardinality constraint $|S|<k$ and a budget constraint $\mathrm{cost}(S)\leq B$. An example of the former is a sensor placement constraint where we want to find the $k$ best sensor locations. An example of the latter is a knapsack problem where we would like to maximize the value of items given a total budget on their weight.
A celebrated result by Nemhauser (1978) proves that the greedy maximization algorithm with cardinality constraints provides a solution that is at least $(1-1/e)\times \mathrm{OPT} \approx 0.632\times \mathrm{OPT}$, i.e. there's a guarantee that the greedy algorithm will do no worse than $(1-1/e)$ of the optimum. Similarly, it can be shown that for a budget constraint using the CELF algorithm, the greedy solution is no worse than $\frac{1}{2}(1-1/e)\times \mathrm{OPT}$. It is the existence of such guarantees that makes submodular optimization very attractive. 
