2024/09/08 by Brandon Van Over, Van Over, Brandon, Bowen Li +5 · 1 citation
Computer Science · #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Electrical engineering #Metaheuristic Optimization Algorithms Research #Network Packet Processing and Optimization #Systems and Control (eess.SY) #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.2409.05020
openalex publication_date 2024/09/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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, αG, αG', and αG'' 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 α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é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.