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

Abstract

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éjols (1984). We consider three constants, $\hat{I}{\pm }_G$, $\hat{I}{\pm }_G^{\prime }$, and $\hat{I}{\pm }_G^{\prime \prime }$ introduced by Conforti and Cornuéjols (1984), that are used in performance bounds of greedy schemes in submodular set optimization. We first generalize both of the $\hat{I}{\pm }_G$ and $\hat{I}{\pm }_G^{\prime \prime }$ 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 $\hat{I}{\pm }_G$ and $\hat{I}{\pm }_G^{\prime \prime }$ bounds and provide a counterexample to show that the $\hat{I}{\pm }_G^{\prime }$ bound is incorrect under the assumptions in Conforti and Cornuéjols (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.

This is the accepted version of the paper for IEEE Transactions on Automatic Control