Results 141 to 150 of about 291 (165)
Some of the next articles are maybe not open access.
Decomposition of submodular functions
Combinatorica, 1983A decomposition theory for submodular functions is described. Any such function is shown to have a unique decomposition consisting of indecomposable functions and certain highly decomposable functions, and the latter are completely characterized. Applications include decompositions of hypergraphs based on edge and vertex connectivity, the decomposition
openaire +1 more source
2011
We introduce the submodular Max-SAT problem. This problem is a natural generalization of the classical Max-SAT problem in which the additive objective function is replaced by a submodular one. We develop a randomized linear-time 2/3-approximation algorithm for the problem. Our algorithm is applicable even for the online variant of the problem.
Yossi Azar, Iftah Gamzu, Ran Roth
openaire +1 more source
We introduce the submodular Max-SAT problem. This problem is a natural generalization of the classical Max-SAT problem in which the additive objective function is replaced by a submodular one. We develop a randomized linear-time 2/3-approximation algorithm for the problem. Our algorithm is applicable even for the online variant of the problem.
Yossi Azar, Iftah Gamzu, Ran Roth
openaire +1 more source
Submodular functions and convexity
1983In “continuous” optimization convex functions play a central role. Besides elementary tools like differentiation, various methods for finding the minimum of a convex function constitute the main body of nonlinear optimization. But even linear programming may be viewed as the optimization of very special (linear) objective functions over very special ...
openaire +1 more source
On submodular function minimization
Combinatorica, 1985zbMATH Open Web Interface contents unavailable due to conflicting licenses.
openaire +1 more source
2017
We study a general stochastic ranking problem where an algorithm needs to adaptively select a sequence of elements so as to “cover” a random scenario (drawn from a known distribution) at minimum expected cost. The coverage of each scenario is captured by an individual submodular function, where the scenario is said to be covered when its function value
Fatemeh Navidi +2 more
openaire +2 more sources
We study a general stochastic ranking problem where an algorithm needs to adaptively select a sequence of elements so as to “cover” a random scenario (drawn from a known distribution) at minimum expected cost. The coverage of each scenario is captured by an individual submodular function, where the scenario is said to be covered when its function value
Fatemeh Navidi +2 more
openaire +2 more sources
On the subdifferential of a submodular function
Mathematical Programming, 1984zbMATH Open Web Interface contents unavailable due to conflicting licenses.
openaire +2 more sources
Using submodularity within column generation to solve the flight-to-gate assignment problem
Transportation Research Part C: Emerging Technologies, 2021Santanu S Dey, John-Paul Clarke
exaly
A note on the implications of approximate submodularity in discrete optimization
Optimization Letters, 2022Andrew Schaefer +2 more
exaly
Beyond pointwise submodularity: Non-monotone adaptive submodular maximization in linear time
Theoretical Computer Science, 2021Shaojie Tang
exaly