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:2^E\to {\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^{\ast })$ 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|\ge (1-\epsilon )K$ and $f(T)\ge (1/2-\epsilon )f(T^{\ast })$. In contrast, previous work only guarantees a value of $\Omega (\epsilon )f(T^{\ast })$ while ensuring that $|T|\ge (1-\epsilon )K$.