We consider an optimization problem where the decision variable is a string of bounded length. For some time there has been an interest in bounding the performance of the greedy strategy for this problem. Here, we provide weakened sufficient conditions for the greedy strategy to be bounded by a factor of (1 − (1 − 1 K)K), where K is the optimization horizon length. Specifically, we introduce the notions of K-submodularity and K-GO-concavity, which together are sufficient for this bound to hold. By introducing a notion of curvature η ∈ (0; 1), we prove an even tighter bound with the factor (1 η)(1−e−η). Finally, we illustrate the strength of our results by considering two example applications. We show that our results provide weaker conditions on parameter values in these applications than in previous results.
Consider the problem of choosing a string of actions to optimize an objective function that is string submodular. It was shown in previous papers 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 @math -approximation to the optimal strategy. This paper improves this approximation by introducing additional constraints on curvature, namely, total backward curvature, total forward curvature, and elemental forward curvature. We show that if the objective function has total backward curvature @math , then the greedy strategy achieves at least a @math -approximation of the optimal strategy. If the objective function has total forward curvature @math , then the greedy strategy achieves at least a @math -approximation of the optimal strategy. Moreover, we consider a generalization of the diminishing-return property by defining the elemental forward curvature. We also introduce the notion of string-matroid and consider the problem of maximizing the objective function subject to a string-matroid constraint. We investigate two applications of string submodular functions with curvature constraints: 1) choosing a string of actions to maximize the expected fraction of accomplished tasks; and 2) designing a string of measurement matrices such that the information gain is maximized. The problem of 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 curvature, namely, total backward curvature, total forward curvature, and elemental forward curvature. We show that if the objective function has total backward curvature σ, then the greedy strategy achieves at least a 1 σ(1 - e-σ)-approximation of the optimal strategy. If the objective function has total forward curvature c, then the greedy strategy achieves at least a (1 - e)-approximation of the optimal strategy. Moreover, we consider a generalization of the diminishing-return property by defining the elemental forward curvature. We also introduce the notion of string-matroid and consider the problem of maximizing the objective function subject to a string-matroid constraint.