Metraipolis › archive › dc_307ede4ee9d8

If it is Good Then Drop it -- a Spiteful Poisson Process for Submodular Maximization — arXiv:2608.05062

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.05062
License (as archived)
CC0-1.0
Archived
2026-10-31T11:58:22.730Z
SHA-256 of the archived text
b50b702c0b69b208e0645389c67f813a61db890ce794548185dbd5e024bf8eb5
Stable URL of this page
https://metraipolis.com/documento/dc_307ede4ee9d8

How to cite

If it is Good Then Drop it -- a Spiteful Poisson Process for Submodular Maximization — arXiv:2608.05062 — arXiv (en), https://arxiv.org/abs/2608.05062 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_307ede4ee9d8 (Metraipolis archive dc_307ede4ee9d8, sha256 b50b702c0b69b208e0645389c67f813a61db890ce794548185dbd5e024bf8eb5)
BibTeX
@misc{dc307ede4ee9d8,
  title = {If it is Good Then Drop it -- a Spiteful Poisson Process for Submodular Maximization — arXiv:2608.05062},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.05062},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_307ede4ee9d8; sha256 b50b702c0b69b208e0645389c67f813a61db890ce794548185dbd5e024bf8eb5},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.05062. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We study the problem of maximizing a general and not necessarily monotone submodular function subject to a matroid independence constraint. This problem has a rich history, with multiple algorithms using both discrete and continuous methods. Recently, [Ganz-Rozenman, Kulik, Schwartz and Singh STOC `26] presented a novel hybrid approach based on a Poisson process that aims to combine the strengths of both discrete and continuous methods for the special case of the problem where the submodular function is monotone. Our main result is a new Poisson process based hybrid algorithm that works for both non-monotone and monotone submodular functions, achieving an approximation of $ \frac{1}{e}$ for the former and $1-\frac{1}{e}$ for the latter. The algorithm always maintains a feasible set and at random times governed by the Poisson process it performs a single element swap based on a best response set. The new idea is that our algorithm is spiteful as it can purposefully discard an element that is in both the current set and the best response set. Surprisingly, this spiteful step does not harm the approximation our algorithm achieves for monotone submodular functions but is necessary for the non-monotone case. As applications, we obtain fast approximation algorithms for maximizing non-monotone submodular function subject to a general matroid independence constraint as well as faster algorithms for a partition matroid.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-06 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2608.05062 — 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-31T11:47:39.825Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-08-06?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).