Submodular Maximization over Bipartite Perfect Matchings and Matroid Intersection Bases

Abstract

Motivated by applications in fairness and foundational questions, we consider the problem of maximizing a monotone submodular function $f\colon 2^E \rightarrow \mathbb{R}_+$ over maximum cardinality sets in the intersection of two matroids on a common ground set $E$. An important special case is submodular perfect matching in bipartite graphs. Prior to this work, its approximability was poorly understood with only constant inapproximability known, despite not even a $\frac{1}{o(\sqrt{|E|})}$-approximation being known. Even when allowing to violate the cardinality constraint slightly, only a bicriteria approximation with a significant loss in the objective was known. Here, we obtain two results. First, we show that, within constant factors, the problem is approximation-equivalent to Submodular Orienteering in directed graphs. This yields an $\Omega(1 / \log |E|)$-approximation in quasi-polynomial time together with an almost-matching hardness result. Second, we obtain an improved polynomial-time bicriteria approximation via a local search framework. More precisely, if $f(T^*)$ is the largest submodular value of a common independent set in both matroids of size at least $K$, we find a common independent set $T$ such that $|T| \geq (1 - \epsilon) K$ and $f(T) \geq (1/2 - \epsilon) f(T^*)$. In contrast, previous work only guarantees a value of $\Omega(\epsilon) f(T^*)$ while ensuring that $|T| \geq (1 - \epsilon) K$.