An Improved Greedy Curvature Bound for Finite-Horizon String Optimization in Sensor Coverage Problem

We study the optimization problem of choosing strings of finite length to maximize string submodular functions on string matroids, which is a broader class of problems than maximizing set submodular functions on set matroids. We provide a lower bound for the performance of the greedy algorithm in our problem, and then prove that our bound is superior to the Greedy curvature based bound proposed by Conforti and Cornu\'ejols. Our bound is also more computationally feasible than most previously proposed curvature based bounds. Finally, we demonstrate the strength of our result on a discrete version sensor coverage problem.