Metraipolis › archive › dc_b30319007963
On the Approximation Relationship between Optimizing Ratio of Submodular (RS) and Difference of Submodular (DS) Functions — arXiv:2101.01631
- Source
- arXiv
- Original
- https://arxiv.org/abs/2101.01631
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-06T05:31:49.893Z
- SHA-256 of the archived text
09bdc93d0285d2011cbd1535203d262e8728695f7444b7bdd3dbb168e8fafaea- Stable URL of this page
https://metraipolis.com/documento/dc_b30319007963
How to cite
On the Approximation Relationship between Optimizing Ratio of Submodular (RS) and Difference of Submodular (DS) Functions — arXiv:2101.01631 — arXiv, https://arxiv.org/abs/2101.01631 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_b30319007963 (Metraipolis archive dc_b30319007963, sha256 09bdc93d0285d2011cbd1535203d262e8728695f7444b7bdd3dbb168e8fafaea)
BibTeX
@misc{dcb30319007963,
title = {On the Approximation Relationship between Optimizing Ratio of Submodular (RS) and Difference of Submodular (DS) Functions — arXiv:2101.01631},
howpublished = {arXiv},
url = {https://arxiv.org/abs/2101.01631},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_b30319007963; sha256 09bdc93d0285d2011cbd1535203d262e8728695f7444b7bdd3dbb168e8fafaea},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv, https://arxiv.org/abs/2101.01631. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We demonstrate that from an algorithm guaranteeing an approximation factor for the ratio of submodular (RS) optimization problem, we can build another algorithm having a different kind of approximation guarantee -- weaker than the classical one -- for the difference of submodular (DS) optimization problem, and vice versa. We also illustrate the link between these two problems by analyzing a \textsc{Greedy} algorithm which approximately maximizes objective functions of the form $\Psi(f,g)$, where $f,g$ are two non-negative, monotone, submodular functions and $\Psi$ is a {quasiconvex} 2-variables function, which is non decreasing with respect to the first variable. For the choice $\Psi(f,g)\triangleq f/g$, we recover RS, and for the choice $\Psi(f,g)\triangleq f-g$, we recover DS. To the best of our knowledge, this greedy approach is new for DS optimization. For RS optimization, it reduces to the standard \textsc{GreedRatio} algorithm that has already been analyzed previously. However, our analysis is novel for this case.
Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Machine Learning (cs.LG); Machine Learning (stat.ML).
Pagina del lavoro: https://arxiv.org/abs/2101.01631 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-06T05:27:05.917Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).