# Tag Info

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