k-Submodular Cover Problem with a Matroid Constraint

概要

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.

参考リンク

• Paper ↗

リンク先のライセンス・再現性・データ条件をご確認ください。自動分類や実装の目安は保証ではありません。

実装を始めるプロンプト

参考リンクを確認したうえで、次の内容をコピーして利用できます。

# 論文・記事
k-Submodular Cover Problem with a Matroid Constraint

# 概要
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…

# 原典
https://arxiv.org/abs/2610.26989

上記の手法を実装してください。実行前に依存関係とライセンスを確認してください。