An Improved Greedy Curvature Bound in Finite-Horizon String Optimization with Application to a Sensor Coverage Problem Article Swipe

MAKE IMPACT

Brandon Van Over , Bowen Li , Edwin K. P. Chong , Ali Pezeshki · YOU? · · 2023 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2308.15758

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 bound of Conforti and Cornuejols. Our bound has lower computational complexity than most previously proposed curvature bounds. Finally, we demonstrate the strength of our result on a sensor coverage problem.

Type

preprint

Language

en

Landing Page

http://arxiv.org/abs/2308.15758

PDF

https://arxiv.org/pdf/2308.15758

OA Status

green

Related Works

10

OpenAlex ID

https://openalex.org/W4386348054

Raw OpenAlex JSON