Metraipolis › archive › dc_cee7596b2fb5

Submodular and strongly submodular functions and diversities — arXiv:2608.11468

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.11468
License (as archived)
CC0-1.0
Archived
2026-10-19T05:47:38.021Z
SHA-256 of the archived text
34aef6e2bc6a8a283c78fde7e3b66b405a52e57c569cb6d9977bf5bd40171cd2
Stable URL of this page
https://metraipolis.com/documento/dc_cee7596b2fb5

How to cite

Submodular and strongly submodular functions and diversities — arXiv:2608.11468 — arXiv (en), https://arxiv.org/abs/2608.11468 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_cee7596b2fb5 (Metraipolis archive dc_cee7596b2fb5, sha256 34aef6e2bc6a8a283c78fde7e3b66b405a52e57c569cb6d9977bf5bd40171cd2)
BibTeX
@misc{dccee7596b2fb5,
  title = {Submodular and strongly submodular functions and diversities — arXiv:2608.11468},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.11468},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_cee7596b2fb5; sha256 34aef6e2bc6a8a283c78fde7e3b66b405a52e57c569cb6d9977bf5bd40171cd2},
  year = {2026}
}

Archived text

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

Submodular functions and their close relatives play a key role in combinatorial optimization, decision theory and potential theory. Part of their importance and usefulness stems from the connections with convex functions and polytopes. Here we explore connections between these functions and metric theory, with the bridge provided by diversities, a recently developed generalization of metric spaces to (finite) sets rather than just pairs. Both submodular functions and strongly submodular functions correspond to natural classes of diversities. Submodular diversities, as we define them here, are essentially non-decreasing, intersecting submodular functions which vanish on singletons. We prove new geometric embedding results for these diversities. In particular we show that submodular, strongly submodular, and XOS functions can be represented by the generalized circumradius, a set function in convex analysis equal to the amount a given convex body needs to be stretched to cover a set of points.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-13 in math.CO).
Categorie arXiv: Combinatorics (math.CO) ; Metric Geometry (math.MG).
Pagina del lavoro: https://arxiv.org/abs/2608.11468 — 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-19T05:40:33.637Z dalla pagina https://arxiv.org/catchup/math.CO/2026-08-13?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).