On Bounds for Greedy Schemes in String Optimization based on Greedy Curvatures

April 10, 2024 Β· Declared Dead Β· πŸ› IEEE Conference on Decision and Control

πŸ‘» CAUSE OF DEATH: Ghosted
No code link whatsoever

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Bowen Li, Brandon Van Over, Edwin K. P. Chong, Ali Pezeshki arXiv ID 2404.06669 Category eess.SY: Systems & Control (EE) Cross-listed cs.DS Citations 3 Venue IEEE Conference on Decision and Control Last Checked 2 months ago
Abstract
We consider the celebrated bound introduced by Conforti and CornuΓ©jols (1984) for greedy schemes in submodular optimization. The bound assumes a submodular function defined on a collection of sets forming a matroid and is based on greedy curvature. We show that the bound holds for a very general class of string problems that includes maximizing submodular functions over set matroids as a special case. We also derive a bound that is computable in the sense that they depend only on quantities along the greedy trajectory. We prove that our bound is superior to the greedy curvature bound of Conforti and CornuΓ©jols. In addition, our bound holds under a condition that is weaker than submodularity.
Community shame:
Not yet rated
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

πŸ“œ Similar Papers

In the same crypt β€” Systems & Control (EE)

Died the same way β€” πŸ‘» Ghosted