String Submodular Functions With Curvature Constraints
From MaRDI portal
Abstract: The problem of objectively choosing a string of actions to optimize an objective function that is string submodular has been considered in [1]. There it is shown that the greedy strategy, consisting of a string of actions that only locally maximizes the step-wise gain in the objective function achieves at least a (1-e^{-1})-approximation to the optimal strategy. This paper improves this approximation by introducing additional constraints on curvatures, namely, total backward curvature, total forward curvature, and elemental forward curvature. We show that if the objective function has total backward curvature sigma, then the greedy strategy achieves at least a frac{1}{sigma}(1-e^{-sigma})-approximation of the optimal strategy. If the objective function has total forward curvature epsilon, then the greedy strategy achieves at least a (1-epsilon)-approximation of the optimal strategy. Moreover, we consider a generalization of the diminishing-return property by defining the elemental forward curvature. We also consider the problem of maximizing the objective function subject to general a string-matroid constraint. We investigate an applications of string submodular functions with curvature constraints.
Cited in
(7)- A unifying look at sequence submodularity
- Exploiting submodularity to quantify near-optimality in multi-agent coverage problems
- Performance bounds with curvature for batched greedy optimization
- Calibrated recommendations for users with decaying attention
- Improved bounds for the greedy strategy in optimization problems with curvature
- Submodular optimization problems and greedy strategies: a survey
- Multi-objective evolutionary algorithms are generally good: maximizing monotone submodular functions over sequences
This page was built for publication: String Submodular Functions With Curvature Constraints
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2980629)
