Summary
This paper studies how to best choose a set of items that follow certain rules, to maximize a special kind of value called a 'submodular function,' which represents benefits with diminishing returns. The authors focus on cases where these items must form perfect matchings in bipartite graphs or satisfy two matroid constraints, which generalize many real-world pairing or selection problems. They reveal new connections to a known hard problem called submodular orienteering, leading to improved approximation methods. Their new technique also finds nearly optimal solutions that slightly relax size constraints but achieve much better value than previous approaches.
What this means in practice
- •For network schedulers: Optimize resource allocations that must meet multiple constraints while maximizing fairness or efficiency using improved submodular maximization techniques under matroid intersections.
- •For market designers: Design better fair matching rules in bipartite markets using improved algorithms that balance match size and quality measured by submodular objectives.
A theory result. No direct application yet.
Authors
Chandra Chekuri, Lars Rohwedder, Neta Singer, Jan Vondrák, Rico Zenklusen
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 $Ω(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 - ε) K$ and $f(T) \geq (1/2 - ε) f(T^*)$. In contrast, previous work only guarantees a value of $Ω(ε) f(T^*)$ while ensuring that $|T| \geq (1 - ε) K$.