Search type Search syntax
Tags [tag]
Exact "words here"
Author user:1234
user:me (yours)
Score score:3 (3+)
score:0 (none)
Answers answers:3 (3+)
answers:0 (none)
isaccepted:yes
hasaccepted:no
inquestion:1234
Views views:250
Code code:"if (foo != bar)"
Sections title:apples
body:"apples oranges"
URL url:"*.example.com"
Bookmarks inbookmarks:mine
inbookmarks:1234
Status closed:yes
duplicate:no
migrated:no
wiki:no
Types is:question
is:answer
Exclude -[tag]
-apples
For more details on advanced search visit our help page
Results tagged with
Search options user 40

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.

4
votes
0answers
Submodularity directly implies the following inequality, for $k \in \{1,\ldots,n-1\}$: $$ F(k) \geq \frac{1}{2} F(k+1) + \frac{1}{2} F(k-1). $$ Imagine applying this inequality over and over again, in …
asked May 8 '12 by Yuval Filmus
13
votes
2answers
\end{multline*}$$ Taking $C = A\cup B$, this property implies monotone submodularity. Is this property known? Background This property came up while trying to characterize coverage functions. …
asked Apr 2 '12 by Yuval Filmus
7
votes
Higher-order discrete derivatives of set functions are explored in Submodularity, supermodularity and higher-order monotonicities of pseudo-boolean functions. … \end{multline*} $$ If you put $C = \varnothing$, you get submodularity. …
answered Apr 2 '12 by Yuval Filmus
8
votes
0answers
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 …
asked May 20 '16 by Yuval Filmus
10
votes
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 follo …
answered Feb 23 '15 by Yuval Filmus