2022 Developer Survey is open! Take survey.
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 ...
user avatar
  • 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 ...
user avatar
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....
user avatar
  • 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 ...
user avatar
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 $...
user avatar
  • 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 ...
user avatar
  • 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 =...
user avatar
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$ ...
user avatar
  • 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). $$ ...
user avatar
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.
user avatar
  • 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 ...
user avatar
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 (...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 217

Only top scored, non community-wiki answers of a minimum length are eligible