# 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.

35 questions
Filter by
Sorted by
Tagged with
1 vote
109 views

### A variant of the generalised assignment problem

I am trying to solve this problem: There are $N$ workers and $T$ tasks. Each task can be assigned to at most one worker. Each worker can be assigned any number of tasks. The profit obtained by ...
48 views

• 1,177
372 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 ...
193 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 ...
• 617
1 vote
288 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 ...
• 19
1 vote
96 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$ ...
242 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 ...
• 4,471
232 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 ...
• 14.5k
1k 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$ ...
2k 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 ...
• 7,615
1k views

• 107
133 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 ...
• 101
269 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 ...
• 654
141 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 ...
• 617
1 vote
605 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 ...
504 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 ...
113 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 ...
89 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)$. ...
• 1,130
207 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 ...
• 171
334 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 ...
928 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 f(\mathcal{A}) - \...
• 61
185 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 ...
• 14.5k
376 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 \\...
• 14.5k
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....