# A Performance Bound for the Greedy Algorithm in a Generalized Class of String Optimization Problems

arXiv: https://arxiv.org/abs/2409.05020 · HTML: https://mlsanity.com/paper/2409.05020/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Sep 2024.

## Built on by (most cited first, 2 of 2)

- [A Greedy PDE Router for Blending Neural Operators and Classical Methods](https://mlsanity.com/paper/2509.24814/) (2025)
- [Distributed Online Bandit Submodular Maximization with Bounded Sampling Violations](https://mlsanity.com/paper/2607.00680/) (2026)

## Abstract (arXiv)

We present a simple performance bound for the greedy scheme in string optimization problems that obtains strong results. Our approach vastly generalizes the group of previously established greedy curvature bounds by Conforti and Cornu'ejols (1984). We consider three constants, αG, αG', and αG'' introduced by Conforti and Cornu'ejols (1984), that are used in performance bounds of greedy schemes in submodular set optimization. We first generalize both of the αG and αG'' bounds to string optimization problems in a manner that includes maximizing submodular set functions over matroids as a special case. We then derive a much simpler and computable bound that allows for applications to a far more general class of functions with string domains. We prove that our bound is superior to both the αG and αG'' bounds and provide a counterexample to show that the αG' bound is incorrect under the assumptions in Conforti and Cornu'ejols (1984). We conclude with two applications. The first is an application of our result to sensor coverage problems. We demonstrate our performance bound in cases where the objective function is set submodular and string submodular. The second is an application to a social welfare maximization problem with black-box utility functions.