pipette
ENEnglish

k-Submodular Cover Problem with a Matroid Constraint

Xinru Li, Donglei Du, Qian Liu, Yang Zhou, Min Li

Preprint

En palabras de los autores

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.

Resultado principalEl resumen no menciona limitaciones.

Apareció: miércoles, 21 de octubre. arXiv. Preprint, todavía sin revisión por pares.