Skip to content
Preprint

k-Submodular Cover Problem with a Matroid Constraint

Oct 2026 · 0 citations · 29 references
Computer Science

TL;DR

A matroid extended greedy algorithm is proposed for the k-submodular cover problem, its bi-criteria approximation ratio is analyzed, and an improved approximation ratio under the special case of unit costs is derived.

Abstract

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.

View source

Similar papers

Preprint Oct 2026

Stronger Hardness for Submodular Maximization Subject to a Matroid Constraint

Maximizing a submodular function subject to a matroid constraint is a cornerstone problem in combinatorial optimization. The state-of-the-art algorithm for this problem obtains $0.401$-approximation~\cite{buchbinder2024constrained}, and the state-of-the-art hardness result shows that no polynomial time algorithm can ob...

Moran Feldman, A. Kuhnle · 2 citations
Preprint Sep 2026

On Maximizing a Weakly Submodular Function over a Matroid Constraint via the Greedy Algorithm

We consider the problem of approximately maximizing a weakly submodular function using the standard greedy algorithm, which is known to give tight approximation results for such functions under a cardinality constraint. We show that this is not the case for general matroid constraints. For any $\gamma<1$, we give a fam...

Justin Ward, Moran Feldman · 1 citation
Preprint Oct 2026

A Refined Analysis for Matroid Secretary with Submodular Objectives

We study the matroid secretary problem with a nonnegative monotone submodular objective. Elements arrive in uniformly random order, and every acceptance decision is immediate and irrevocable. We give an $8.699$-competitive algorithm for arbitrary matroids. The algorithm first rejects a randomly sized initial segment of...

Dennis Joyce · 0 citations
Sep 2026

Tight Approximation Results for Matroid Optimization with a Linear Constraint

We study the following class of matroid optimization problems with a linear constraint (P-MOL). Given a matroid M=(E,I), two weight functions $v,w:E\to R_{\ge 0}$, and a threshold $L\in R_{\ge 0}$, find $opt v(S)$ where S is either an independent set or a base of M satisfying a budget-type constraint: $w(S)\le L$ or $w...

Ilan Doron-Arad, H. Shachnai, Gilad Shmerler · 0 citations
Sep 2026

Submodular Maximization over Bipartite Perfect Matchings and Matroid Intersection Bases

It is shown that the problem of maximizing a monotone submodular function over maximum cardinality sets in the intersection of two matroids on a common ground set is approximation-equivalent to Submodular Orienteering in directed graphs and an improved polynomial-time bicriteria approximation is obtained via a local se...

Chandra Chekuri, Lars Rohwedder, Neta Singer et al. · 1 citation
Preprint Oct 2026

From Linear to Polylogarithmic: Dynamic Submodular Maximization over Matroids

This work presents the first fully dynamic algorithm for submodular maximization over matroids with polylogarithmic update time, and maintains a $(4+\epsilon)-approximate solution with expected amortized update time $poly(\log n, \epsilon^{-1})$, where $n = |N|$.

Kiarash Banihashem, Samira Goudarzi, M. Hajiaghayi et al. · 1 citation

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.