10
votes
Are there any interesting open questions having to do with submodularity, specially in the intersection of theoretical machine learning?
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 ...
- 14.1k
6
votes
Accepted
Restriction of a convex function to {0, 1}^n
Any real valued function $g$ defined on $\{0,1\}^n$ can be extended to a convex function over $[0,1]^n$ (it is called the convex closure). See Dughmi's nice survey. The implication for your question ...
- 6,650
6
votes
Accepted
Minimizing a submodular function given noisy oracle access
A FOCS'15 paper by Lee, Sidford, and Wong [LSW15] can be leveraged to obtain such minimization guarantees -- cf. Section 5 (specifically, Corollary 5.4) in our recent paper ([BCELR16]).
Corollary 5....
- 4,331
4
votes
Accepted
When can a convex function induce submodularity?
The notion of sub-modularity you use is non-standard. Usually you consider set functions with domain $\lbrace 0, 1\rbrace^n$. But to answer your questions, the Lovász extension establishes the ...
- 56
4
votes
Accepted
Maximizing a monotone supermodular function s.t. cardinality
I think this is an example showing no kind of approximation is possible except with exponential$(k)$ value queries.
Let $f(S) = 0$ if $|S| \leq k$, otherwise $f(S) = |S| - k$. Now pick a special set $...
- 7,022
4
votes
Accepted
Minimizing entropy plus a modular function
Unless I'm mistaken, you can solve your problem in $O(n\log n)$ time using a greedy algorithm.
Minimizing $f(S)$ is equivalent to maximizing
$$\textstyle g(S') = \sum_{i \in S'} b_i + \big(\sum_{i\in ...
- 8,133
3
votes
Accepted
Properties of convex polytope of 0-1 matrices
Sasho already gave you a yes/no answer, but here's an actual convex combination for you: If $B_\ell$ is the $k \times k$ matrix which is $1$ when $|S_i \cap S_j| \ge \ell$ and zero otherwise, then $M =...
- 1,419
3
votes
Accepted
A maximization problem containing summation and multiplication
I think both of your problems are in P. Here's an algorithm that works in P without any restriction on the $(a_i,b_i)$ pairs.
Formulate your problem as the problem of choosing $x\in\{0,1\}^n$ ...
- 8,133
2
votes
Accepted
Maximum weight matching and submodular functions
Definition. For a given finite set $A$, a set function $f:2^A \rightarrow \mathbb{R}$ is submodular if for any $X, Y \subseteq A$ it holds that:
$$
f(X) + f(Y) \geq f(X \cup Y) + f(X \cap Y).
$$
...
2
votes
Minimizing SubModular Function: Cardinality
It is NP-hard. Svitkina and Fleischer showed that there is no $o(\sqrt{n/\log n})$ approximation using only a polynomial number of queries.
- 4,256
2
votes
Accepted
Monotone supermodular function minimization under partition matroid constraints
Consider a graph $G=(V,E)$. Define the set function $f$ over $V$ where $f(A)$ is the number of edges with both end points in $A$. Then $f$ is supermodular and monotone. Suppose $G$ has an independent ...
- 6,650
1
vote
Reference request --- minimizing a non-increasing submodular function with (upper bound) cardinality constraint
If the only thing that you know about $f$ is that it is non-increasing, then there is a simple adversary argument to show that you need to examine the value of $f$ on at least ${n \choose k}$ inputs (...
- 10.3k
1
vote
How to sample from a distribution with submodular weights
There is a paper by Gotovos, Hassani, and Krause (NIPS, 2015) titled "Sampling from Probabilistic Submodular Models" which describes a MCMC method based on Gibbs sampling. They show that the mixing ...
- 111
1
vote
Maximizing difference of a submodular and a modular function
To simplify life, let $\mathcal V = [n] := \{1,2,\ldots,n\}$. For $A \subseteq [n]$, define $h(A):=\sum_{i \in A}c_i$. Note that $h$ defines a modular (i.e additive) set function. Now, suppose there ...
- 217
Only top scored, non community-wiki answers of a minimum length are eligible