.png){kind=icon}
.png){kind=icon}
Return
A Performance Bound for the Greedy Algorithm in a Generalized Class of String Optimization Problems
.png){kind=icon}
PRE
AI
DOI：10.1109/TAC.2025.3626265.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
In this article, we present a simple performance bound for the greedy scheme in string optimization problems. Our approach generalizes the family of greedy curvature bounds established by Conforti and Cornuejols (1984). Specifically, we examine three bounds they introduced for evaluating the performance of the greedy scheme in maximizing monotone submodular set functions. We first generalize two of these bounds to string optimization problems in a manner that includes maximizing monotone submodular set functions as a special case. Next, we derive a simpler and more computable bound that applies to a broader class of functions with string domains. We then prove that our bound is superior to two of their bounds and provide a counterexample to show that the third bound is incorrect under the assumptions in the work of Conforti and Cornuejols (1984). We demonstrate our results through two applications. First, we apply our bound to sensor coverage problems with both monotone set and string submodular objective functions. The second application is a social welfare maximization problem involving a monotone nonsubmodular black-box utility function.
Keywords:
Greedy algorithm
greedy curvature
performance (ratio) bound
sensor coverage
string optimization
subadditivity
submodularity
welfare maximization
Journal
IF:
7
Papers:
1.3W
Citations:
6.7W