Metraipolis › archive › dc_bc0d1c77ea34
k-Submodular Cover Problem with a Matroid Constraint — arXiv:2610.26989
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.26989
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-21T07:13:23.396Z
- SHA-256 of the archived text
991f050a4b29b9067107f8f2033ae3e0b0fcc1a985578f4c7026c12b6251b1e9- Stable URL of this page
https://metraipolis.com/documento/dc_bc0d1c77ea34
How to cite
k-Submodular Cover Problem with a Matroid Constraint — arXiv:2610.26989 — arXiv (en), https://arxiv.org/abs/2610.26989 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_bc0d1c77ea34 (Metraipolis archive dc_bc0d1c77ea34, sha256 991f050a4b29b9067107f8f2033ae3e0b0fcc1a985578f4c7026c12b6251b1e9)
BibTeX
@misc{dcbc0d1c77ea34,
title = {k-Submodular Cover Problem with a Matroid Constraint — arXiv:2610.26989},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.26989},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_bc0d1c77ea34; sha256 991f050a4b29b9067107f8f2033ae3e0b0fcc1a985578f4c7026c12b6251b1e9},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.26989. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We investigate k-submodular cover problem with a matroid constraint on an n-element ground set V , which seeks k disjoint subsets of V with minimal cost, where their union is an independent set for some matroid defined on V and the k-submodular utility function surpasses a specified threshold. This problem generalizes the k-submodular cover problem and has a wide range of applications in artificial intelligence and combinatorial optimization. In this paper, we propose a matroid extended greedy algorithm for this problem, analyze its bi-criteria approximation ratio, and further derive an improved approximation ratio under the special case of unit costs. Tema degli esploratori: economia dei servizi IA (elenco arXiv cs.GT, nuovi lavori del giorno). Categorie arXiv: Computer Science and Game Theory (cs.GT). Pagina del lavoro: https://arxiv.org/abs/2610.26989 — 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-21T07:07:43.125Z dalla pagina https://arxiv.org/list/cs.GT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).