<p>There are many open algorithmic problems. All problems below (other than the last bullet) are NP-hard, so we are interested in the best approximation ratio we can achieve in polynomial time. The following are just a sample:</p>

<ol>
<li><p>Given a non-negative submodular function on a universe $U$, find a set $A$ of size at most $k$ maximizing $f(A)$. The best known approximation ratio is $1/e+0.004$ (<a href="http://www.cs.princeton.edu/~roysch/Papers/SMC-BFNS14.pdf">BFNS14</a>). When "at most" is replaced by "exactly", the best known approximation ratio is 0.356 (also BFNS14).</p></li>
<li><p>Given a non-negative monotone submodular function and $k$ matroids, find a set $A$ belonging to all different matroids and maximizing $f(A)$. When $k=1$ the best approximation ratio is $1-1/e$, and this is optimal. For larger $k$, <a href="http://www2.warwick.ac.uk/fac/sci/dcs/people/maxim_sviridenko/MatroidExchange-MOR_rev2.pdf">LSV</a> give a $1/k$ approximation, but this is probably not tight.</p></li>
<li><p>There are two algorithms for maximizing a non-negative monotone submodular function over a matroid that give the optimal approximation ratio $1-1/e$: the <a href="http://web.engr.illinois.edu/~chekuri/papers/submod_max_journal.pdf">continuous greedy algorithm</a> and the <a href="http://www.cs.toronto.edu/~yuvalf/FilmusWard.pdf">non-oblivious local search algorithm</a>. Both are randomized. The best known deterministic algorithm is the greedy algorithm, giving a $1/2$ approximation. Can we separate deterministic and randomized algorithms in this oracle setting? A similar question arises in the non-monotone unconstrained case, in which <a href="http://www.cs.princeton.edu/~roysch/Papers/USM-BFNS12.pdf">BFNS12</a> give an optimal randomized $1/2$ approximation algorithm, but the best known deterministic algorithms (one in BFNS12 and an earlier local search algorithm due to <a href="http://www.wisdom.weizmann.ac.il/~feige/mypapers/FeigeMirrokniVondrak.pdf">FMV</a>) give only a $1/3$ approximation.</p></li>
<li><p>Both the continuous greedy algorithm and the non-oblivious local search algorithm are rather slow. Is there a fast, $\tilde{O}(n)$ algorithm for maximizing a monotone submodular function over a matroid? (see <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.465.572&amp;rep=rep1&amp;type=pdf">BV</a> for the case of a uniform matroid)</p></li>
<li><p>Algorithms for <em>minimizing</em> submodular functions are also a bit slow, the fastest running in time $O(n^5)$ (see <a href="http://www.zib.eu/groetschel/teaching/PAPER/Iwata2008.pdf">Iwata's survey</a>).</p></li>
</ol>

CC BY-SA 3.0
2015-02-23T19:54:09.400Z
2015-02-23T19:54:09.400Z
Yuval Filmus
<p>I was interested in knowing about open research topics related with sub modularity, specially within its intersection with theoretical machine learning (and related topics). </p>

<p>I am particularly interested in algorithms (specially their application to machine learning, and whenever possible, proving theoretical guarantees for them, wether these guarantees are in complexity or learnability).</p>

<p>I'd be interested in knowing if there are any "heuristic" algorithms out there in the area of sub modularity and machine learning, with unknown guarantees. From my current knowledge of the topic, the most common heuristic seems to be the "greedy" heuristic, and it seems to be quite well understood. Hence, I was wondering if there was any open problems in the area of designing new algorithms (or improving current ones) or algorithms that already exists, that don't have any guarantees. Is there anything open questions related with theoretical guarantees that is open in sub modularity?</p>

<p>Or of if there aren't any such open question, are there any open question in the intersection of sub modularity and machine learning?</p>

<ds.algorithms><approximation-algorithms><machine-learning><open-problem><submodularity>
Are there any interesting open questions having to do with submodularity, specially in the intersection of theoretical machine learning?
Charlie Parker
# Are there any interesting open questions having to do with submodularity, specially in the intersection of theoretical machine learning?

(Asked by: username_0 on 2015-02-23)

I was interested in knowing about open research topics related with sub modularity, specially within its intersection with theoretical machine learning (and related topics).

I am particularly interested in algorithms (specially their application to machine learning, and whenever possible, proving theoretical guarantees for them, wether these guarantees are in complexity or learnability).

I'd be interested in knowing if there are any "heuristic" algorithms out there in the area of sub modularity and machine learning, with unknown guarantees. From my current knowledge of the topic, the most common heuristic seems to be the "greedy" heuristic, and it seems to be quite well understood. Hence, I was wondering if there was any open problems in the area of designing new algorithms (or improving current ones) or algorithms that already exists, that don't have any guarantees. Is there anything open questions related with theoretical guarantees that is open in sub modularity?

Or of if there aren't any such open question, are there any open question in the intersection of sub modularity and machine learning?

**Tags:** ds.algorithms, approximation-algorithms, machine-learning, open-problem, submodularity

---

## 1 answers

### Answer by username_1 on 2015-02-23. Score: 10

There are many open algorithmic problems. All problems below (other than the last bullet) are NP-hard, so we are interested in the best approximation ratio we can achieve in polynomial time. The following are just a sample:

1. Given a non-negative submodular function on a universe $U$, find a set $A$ of size at most $k$ maximizing $f(A)$. The best known approximation ratio is $1/e+0.004$ ([BFNS14](http://www.cs.princeton.edu/~roysch/Papers/SMC-BFNS14.pdf)). When "at most" is replaced by "exactly", the best known approximation ratio is 0.356 (also BFNS14).
2. Given a non-negative monotone submodular function and $k$ matroids, find a set $A$ belonging to all different matroids and maximizing $f(A)$. When $k=1$ the best approximation ratio is $1-1/e$, and this is optimal. For larger $k$, [LSV](http://www2.warwick.ac.uk/fac/sci/dcs/people/maxim_sviridenko/MatroidExchange-MOR_rev2.pdf) give a $1/k$ approximation, but this is probably not tight.
3. There are two algorithms for maximizing a non-negative monotone submodular function over a matroid that give the optimal approximation ratio $1-1/e$: the [continuous greedy algorithm](http://web.engr.illinois.edu/~chekuri/papers/submod_max_journal.pdf) and the [non-oblivious local search algorithm](http://www.cs.toronto.edu/~yuvalf/FilmusWard.pdf). Both are randomized. The best known deterministic algorithm is the greedy algorithm, giving a $1/2$ approximation. Can we separate deterministic and randomized algorithms in this oracle setting? A similar question arises in the non-monotone unconstrained case, in which [BFNS12](http://www.cs.princeton.edu/~roysch/Papers/USM-BFNS12.pdf) give an optimal randomized $1/2$ approximation algorithm, but the best known deterministic algorithms (one in BFNS12 and an earlier local search algorithm due to [FMV](http://www.wisdom.weizmann.ac.il/~feige/mypapers/FeigeMirrokniVondrak.pdf)) give only a $1/3$ approximation.
4. Both the continuous greedy algorithm and the non-oblivious local search algorithm are rather slow. Is there a fast, $\tilde{O}(n)$ algorithm for maximizing a monotone submodular function over a matroid? (see [BV](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.465.572&rep=rep1&type=pdf) for the case of a uniform matroid)
5. Algorithms for *minimizing* submodular functions are also a bit slow, the fastest running in time $O(n^5)$ (see [Iwata's survey](http://www.zib.eu/groetschel/teaching/PAPER/Iwata2008.pdf)).


---

