Submodular set function - Open Access .click

Mathematics of Operations Research, 1978
A real-valued function z whose domain is all of the subsets of N = {1, …, n) is said to be submodular if z(S) + z(T) ≥ z(S ∪ T) + z(S ∩ T), ∀S, T ⊆ N, and nondecreasing if z(S) ≤ z(T), ∀S ⊂ T ⊆ N. We consider the problem maxS⊂N {z(S): |S| ≤ K, z submodular and nondecreasing, z(Ø) = 0}.
G L Nemhauser
exaly +3 more sources

Submodular Function Minimization with Submodular Set Covering Constraints and Precedence Constraints

Lecture Notes in Computer Science, 2018
In this paper, we consider the submodular function minimization problem with submodular set covering constraints and precedence constraints, and we prove that the algorithm of McCormick, Peis, Verschae, and Wierz for the precedence constrained covering problem can be generalized to our setting.
Kamiyama Naoyuki, Naoyuki Kamiyama
exaly +2 more sources

A note on maximizing a submodular set function subject to a knapsack constraint

Operations Research Letters, 2004
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Maxim Sviridenko
exaly +2 more sources

fos: computer and information sciences
submodular function
combinatorial optimization

approximation algorithm
data structures and algorithms cs.ds
computer science - data structures and algorithms

fos: mathematics
16. peace & justice
submodular optimization