13
There is a complete characterization of coverage functions in terms of such equations. For |X|>3 there are more equations than the ones pointed. Each of these equations can be thought as a constraint on discrete $k^{th}$ derivative.
Monotone increase function if and only if first order discrete derivative is +ve. i.e. $f(B)-f(A)\ge 0$ when $A\subseteq B$.
...
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:
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 ...
10
The problem is likely to be hard to approximate. The densest bipartite subgraph problem can be cast as a special case. Given a bipartite graph $(V,E)$ where $V=V_1 \uplus V_2$ define $f(S,T)$ for $S \subseteq V_1, T \subseteq V_2$ to be the number of edges between $S$ and $T$. Then $f$ satisfies the desired property. In fact $f(S,\cdot)$ is modular and so is ...
7
Higher-order discrete derivatives of set functions are explored in Submodularity, supermodularity and higher-order monotonicities of pseudo-boolean functions. According to them, the strict third-order discrete derivative condition is
$$
\begin{multline*}
f(A \cap B) + f(A \cap C) + f(B \cap C) + f((A \cap B) \cup (A \cap C) \cup (B \cap C)) \geq \\
f(A \...
6
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. Let $g\colon 2^{[m]} \to \mathbb{R}$ be a submodular function. There exists an algorithm that, when given access to an approximate oracle $\mathcal{O}^{\pm}...
5
Take an arbitrary element $e \in \Omega$. If $f(e) = f_{\Omega-e}(e)$ then $e$ is not affected by the rest of the elements so we can choose $X_1 = \{e\}$ and $X_2 = \Omega-\{e\}$. Otherwise let $X$ be an inclusion-wise minimal subset of $\Omega-e$ such that $f(e) > f_X(e)$. Then $X \cup \{e\}$ should be in the same partition. If $X \cup \{e\} = \Omega$ we ...
4
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 S'} \alpha_i\big) \log \sum_{j \in S'} \alpha_j$$
for $b_i=w_i + \alpha_i\log(\alpha_i)$. Here $S'$ is the complement of your $S$.
Assume WLOG that $\alpha_i&...
4
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 following relationship between sub-modularity and convexity:
A set-function $F$ is sub-modular if and only if its Lovász extension $f$ is convex. For a proof see ...
4
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 $S^*$ uniformly at random from all sets of size $k$, and let $f(S^*) = 0.5$.
I'm claiming that this function is supermodular because every element initially ...
3
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$ subject to $\sum_i x_i = k$ so as to maximize
$$\textstyle f(x) = \pi(x) + \sum_i x_i a_i$$
where $\pi(x)=\prod_i \exp( x_i \beta_i)$ and $\beta_i = \ln b_i$. Relax ...
3
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 = \sum_{\ell=1}^{n'} \frac{1}{n'} B_\ell$.
2
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.
2
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 set of size $k$. Then the minimum of $f(S)$ under the constraints $|S| = k$ (the uniform matroid constraint) will be $0$. If $G$ does not have an independent ...
1
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 (e.g., all ${n \choose k}$ different sets of cardinality $k$) in the worst case. For instance, consider functions $f$ that are $+\infty$ on all sets of ...
1
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).
$$
Lemma
Given a bipartite graph $G = (A \cup B, E)$ with positive edge weights, let $f: 2^A \rightarrow \mathbb{R}^+$ be the function that maps $S\subseteq A$ to ...
1
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 time $t_{\text{mix}}(\epsilon)$ is bounded above by
$$ t_{\text{mix}}(\epsilon) \leq 2 n^2 \exp(\zeta_f) \log \left( \frac{1}{\epsilon p_\min} \right) $$
where $...
Only top voted, non community-wiki answers of a minimum length are eligible
