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,979
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,451
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 ...
- 9,595
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,595
3
votes
Accepted
A bound that follows from submodularity
The following lemma implies the inequality in question.
Lemma 1. $E[f_{R\setminus \{a\}}(a)] \le E[f_{R\setminus\{a\}}(a) \,|\, a \in R]$
Proof. Consider the following experiment:
Let $R$ be ...
- 9,595
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$ ...
- 9,595
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,429
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
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 ...
- 291
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,367
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,979
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 (...
- 11.7k
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
Only top scored, non community-wiki answers of a minimum length are eligible