On Bounds for Greedy Schemes in String Optimization based on Greedy Curvatures
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909308265955328 |
|---|---|
| author | Li, Bowen Van Over, Brandon Chong, Edwin K. P. Pezeshki, Ali |
| author_facet | Li, Bowen Van Over, Brandon Chong, Edwin K. P. Pezeshki, Ali |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_06669 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On Bounds for Greedy Schemes in String Optimization based on Greedy Curvatures Li, Bowen Van Over, Brandon Chong, Edwin K. P. Pezeshki, Ali Systems and Control Data Structures and Algorithms 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. |
| title | On Bounds for Greedy Schemes in String Optimization based on Greedy Curvatures |
| topic | Systems and Control Data Structures and Algorithms |
| url | https://arxiv.org/abs/2404.06669 |