Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [submodularity]

In mathematics, submodular functions are set functions which usually appear in approximation algorithms, functions modeling user preferences in game theory,economics, combinatorial optimization, electrical networks and operations research.

1
vote
1answer
56 views

Reference request — minimizing a non-increasing submodular function with (upper bound) cardinality constraint

Suppose a set function $f(S)$ is submodular and non-increasing, meaning that for any $S'\subset S$, $f(S') \geq f(S)$. The problem is to minimize $f(S)$ s.t. $|S| \leq k$. I am wondering if there are ...
1
vote
0answers
48 views

maximization of non-negative monotone supermodular set function with cardinality constraints

the following link Maximizing a monotone supermodular function s.t. cardinality says no kind approximation possible for maximizing non negative supermodular function subject to maximum cardinality ...
0
votes
0answers
89 views

maximizing monotone supermodular function with cardinality constraints

I am new to submodular functions. I want to maximize monotone supermodular function under cardinality constraint,i.e.,let $v=\{1,2,...n\}$, $f:2^v\rightarrow R$ which is monotone super modular ...
0
votes
0answers
94 views

Reverse greedy for monotone submodular maximization under cardinality constraint

Consider the classic problem of maximizing a monotone submodular set function $f(A)$ under the cardinality constraint $|A| \leq k$. This problem can be posed as maximizing $f(S\setminus B)$ subject ...
1
vote
1answer
90 views

Minimizing SubModular Function: Cardinality

Given a submodular function f: 2^V to reals (not necessarily monotone), and an integer k, find a set S such that |S| <= k and such that f(S) is minimized. When the size constraint is |S| >=k, the ...
4
votes
0answers
35 views

Approximating a monotone submodular function using a concrete coverage function

Is it possible to approximate a monotone submodular function using a concrete coverage function, i.e. Given a ground set $U$ and a monotone submodular function, $f:2^U\to \mathbb{R}$, the goal is to ...
0
votes
0answers
28 views

Submodular functions over a multi-value (non-binary) domain

Classically, the domain of submodular functions is $2^{[n]}$. Is there any work with trying to extend them to domains such as $[k]^{[n]}$. Note: I am aware of the Lovasz extension that defines them ...
1
vote
1answer
105 views

Monotone supermodular function minimization under partition matroid constraints

Is there a known approximation algorithm for the problem of minimizing a monotone (non increasing) supermodular function under partition matroid constraints ?
2
votes
0answers
46 views

On the impossibility of representing/approximating subadditive function using additive functions

I am trying to understand whether a monotone and subadditive function $f(S), S \subseteq 2^{[n]}$ and $ f : 2^{[n]} \rightarrow R_{\geq0}$ can be represented using an additive function $\hat{f}(S) = \...
12
votes
0answers
226 views

Extreme rays of the cone of submodular functions

Consider a ground set $U=\{1,2,...,n\}$ and the set $\mathcal{F}$ of all non-negative submodular functions $f: 2^U \mapsto \mathbb{R}_{\geq 0}$. The set $\mathcal{F}$ is closed under taking linear ...
7
votes
1answer
144 views

Minimizing entropy plus a modular function

I have a question about whether there are faster algorithms for specific submodular minimization problems. In particular, I am trying to find a fast algorithm for minimizing the following set ...
0
votes
0answers
197 views

Submodularity of KL divergence

Entropy on a set of random variables is known to be submodular. Now given a set of random variables $P_1, P_2, P_3, \dots, P_N$ and $Q_1, Q_2, Q_3, \dots, Q_N$, where every $P_i$ is a true ...
1
vote
0answers
168 views

Maximize the weight of MST + sum of vertex weights

I am considering a problem where the goal is to choose a subset of size $k$ of the vertices in a graph, such that the weight of their minimum spanning tree + the sum of their vertex weights is ...
1
vote
1answer
91 views

Properties of convex polytope of 0-1 matrices

Problem setting Consider a set $ S = \big\{ 1,2,\cdots,n \big\}$. Now consider $k$ equal-sized subsets $S_i \subset S$ s.t of size $\big|S_i\big|=n' \;\forall i$. Consider a $k\times k$ matrix $M$ ...
6
votes
1answer
202 views

Minimizing a submodular function given noisy oracle access

Let $f\colon 2^{[n]} \to \mathbb{R}$ be a submodular function (one can assume $f$ is bounded, if this helps). We are given noisy oracle access to $f$: on any $S$ and for any $\tau > 0$, one can ...
9
votes
0answers
154 views

NP-hardness of approximation for unconstrained submodular maximization

The problem of unconstrained submodular maximization can be phrased as follows: Given a non-negative submodular function $f$ on a domain $D$ find a set $S \subseteq D$ maximizing $f(S)$. Here a ...
11
votes
1answer
532 views

Maximum weight matching and submodular functions

Given a bipartite graph $G = (U \cup V, E)$ with positive weights let $f: 2^U \rightarrow \mathbb{R}$ with $f(S)$ equal to the maximum weight matching in the graph $G[S\cup V]$. Is it true that $f$ ...
5
votes
1answer
642 views

Maximizing a monotone supermodular function s.t. cardinality

I've tried to comb the literature and seen a lot of references to results that almost but don't quite seem to address this. Question: Is it known to be true or is there a hardness result ...
3
votes
0answers
365 views

Minimizing a monotone submodular function under a cardinality constraint

I would like to know what the status of the following question is: Given query access to a non-decreasing, non-negative submodular function $f\colon 2^{[n]} \to \mathbb{R}$ and a parameter $0 \leq ...
3
votes
1answer
183 views

A maximization problem containing summation and multiplication

Are the following two problems NP-hard? Problem 1 Given $n$ ordered pairs of integers $S=\{(a_i,b_i)\}$, $1\leq i \leq n$, and an integer $k$. Find a subset $A$ of $S$ with $k$ elements, such that $...
0
votes
0answers
112 views

Maximize number of bins and minimize cost of elements chosen from a set

I am considering the following problem: there is a set of elements $S$ where each element is assigned to a bin $B$. The bins are disjoint and their union is $S$. There is also a cost function ...
2
votes
1answer
161 views

When can a convex function induce submodularity?

Say I have a real valued convex function $f$ on the hypercube $[-1,1]^n$. Let $f'$ be the induced function on the discrete hypercube $\{-1,1\}^n$. Now I want to find a vertex on $\{-1,1\}^n$ on which ...
5
votes
0answers
84 views

How to sample from a distribution with submodular weights

Is there a known algorithm for sampling a set $S \subset \{1,...,n\}$ with probability $p_S = \frac{e^{f(S)}}{\sum_{T \subset \{1,...,n\}} e^{f(T)}}$ where $f: 2^{\{1,...,n\}} \to \mathbb{R}$ is a ...
0
votes
0answers
381 views

Hardness of Minimizing Submodular Functions with Cardinality Constraints

I am new to submodular functions and I am reading the introductions to submodular functions and applications ( https://www.ima.umn.edu/optimization/seminar/queyranne.pdf ). In this introduction, it ...
7
votes
1answer
401 views

Are there any interesting open questions having to do with submodularity, specially in the intersection of theoretical machine learning?

I was interested in knowing about open research topics related with sub modularity, specially within its intersection with theoretical machine learning (and related topics). I am particularly ...
5
votes
0answers
102 views

Maximizing a submodular function with restricted values

Maximizing a general monotone submodular function $f$ under the constraint that $|S|\leq k$, can be approximated to $(1-1/e)$. I am wondering if a better approximation algorithm exists if the ...
2
votes
0answers
81 views

Name for the “stronger submodularity” property in cut function

Let $f:2^V \rightarrow \mathbb{R}$ be a set function over $V$ that satisfies the following: $f(A \cap B) + f(A \cup B) \le f(A) + f(B)$ $f(A \backslash B) + f(B \backslash A) \le f(A) + f(B)$. ...
4
votes
0answers
165 views

Submodular function re-optimization (after an update)

The problem I have is as follows: I know the minimizer/minimum of a non-negative submodular function, and want to use this to efficiently compute the minimizer/minimum of a "perturbed" submodular ...
8
votes
1answer
254 views

Maximizing a submodular function of two sets with different size constraints

I have two totally distinct domains (apples and oranges) and I have a function $f$ that takes a set of objects from the first domain and a set of objects from the second domain and returns a real ...
5
votes
0answers
382 views

Maximizing difference of a submodular and a modular function

I'm considering a network planning problem which is stated as follows: From the given ground set $\mathcal{V}$, select $\mathcal{A} \subseteq \mathcal{V}$ such that \begin{equation} f(\mathcal{A}) - \...
4
votes
0answers
164 views

Term rewriting for proving inequalities

Suppose $f$ is a submodular set function on a universe $U$ of size $n$. For $k \in \{0,\ldots,n\}$, let $$ F(k) = \operatorname*{\mathbb{E}}_{X \in \binom{U}{k}} f(X), $$ where $\binom{U}{k}$ is the ...
13
votes
2answers
329 views

Strengthenings of submodularity

A set-function $f$ is monotone submodular if for all $A,B$, $$ f(A) + f(B) \geq f(A \cup B) + f(A \cap B). $$ A stronger property is $$ \begin{multline*} f(A) + f(B) + f(C) + f(A\cup B\cup C) \geq \\...
9
votes
1answer
333 views

Decomposing a submodular function

Given a submodular function $f$ on $\Omega=X_1\cup X_2$ where $X_1$ and $X_2$ are disjoint and $f(S)=f_1(S\cap X_1)+f_2(S\cap X_2)$. Here $f_1$ and $f_2$ are submodular on $X_1$ and $X_2$ respectively....