4
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.