Research map / Learning theory and algorithms / Fairness
Improved Algorithms for Fair Matroid Submodular Maximization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives a randomized and a deterministic algorithm for fair monotone matroid submodular maximization that meet (1-epsilon) of each fairness lower bound in expectation while keeping upper bounds exact, evaluated on coverage, clustering and movie recommendation.
Problem
Monotone submodular maximization under a matroid constraint combined with group fairness lower and upper bounds; prior algorithms only guarantee half of each lower bound (or only in expectation with violated upper bounds), and perfect matching constraints (l=1) had no guarantee.
Approach
Starts from a high-value upper-fair independent set and a maximum fair independent set P, then iteratively applies randomly chosen disjoint augmenting or alternating matroid-intersection exchange paths to trade value for fairness, so that about (1-epsilon) of the fairness deficit is removed in expectation.
Key results
- Theoretically, for any epsilon, the randomized algorithm satisfies E[|S ∩ V_c|] ≥ (1-epsilon) l_c with upper bounds satisfied exactly and E[f(S)] ≥ 0.499·epsilon·OPT.
- In experiments, Our(0.2) and Our(0.5) dominate TwoPass on both objective and fairness violation in coverage and movie recommendation scenarios.
- In clustering results are unclear and TwoPass generally does better; UBMI attains highest objective but largest fairness violations.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed algorithm rather than prior work and natural baselines | FMMSM · Graph coverage (Pokec) | submodular objective value | Helped |
| Use the proposed algorithm rather than prior work and natural baselines | FMMSM · Recommender system (Movielens 1M) | submodular objective value | Helped |
| Use the proposed algorithm rather than TwoPass | FMMSM · Graph coverage (Pokec) | fairness violation | Helped |
| Use the proposed algorithm rather than TwoPass | FMMSM · Recommender system (Movielens 1M) | fairness violation | Helped |
| Use the proposed algorithm rather than TwoPass | FMMSM · Exemplar-based clustering | submodular objective value | Mixed |
| Increase ε (ablation) | Our randomized algorithm · Graph coverage, clustering, and recommender system | fairness violation | Mixed |
| Use Greedy instead of local search to construct the high-value set (ablation) | Our randomized algorithm · FMMSM | approximation ratio: 0.499 -> 1/3 | Hurt |
Surprising findings
- For clustering, the proposed method does not clearly outperform the TwoPass baseline.
Limitations
- Guarantee on objective value is only 0.499·epsilon of OPT, with the O(epsilon) loss unavoidable relative to the fair optimum.
- Experiments use simplified greedy subroutines that ignore the objective when building the fair set, so practical values are not fully optimized.
- Open problem of constant-factor approximation for MSPM without fairness violation remains unresolved.
Experimental setup
Datasets: Pokec social network Portuguese bank marketing dataset MovieLens 1M
Benchmarks: Pokec graph coverage bank marketing exemplar-based clustering MovieLens 1M recommendation
Metrics: submodular objective value total fairness violation
Baselines: TwoPass LBMI UBMI Random
Builds on: matroid intersection exchange graph greedy algorithm for submodular maximization under matroid two-pass fair matroid submodular algorithm
Closest papers by meaning
- Fairness in Streaming Submodular Maximization over a Matroid Constraint (ICML 2023 · similarity 0.93)
- Fair Submodular Cover (ICLR 2025 · similarity 0.90)
- An Asymptotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale (ICML 2025 · similarity 0.88)
- Discretely beyond $1/e$: Guided Combinatorial Algortihms for Submodular Maximization (NeurIPS 2024 · similarity 0.88)
- Online Two-Stage Submodular Maximization (NeurIPS 2025 · similarity 0.86)
- The Price of Opportunity Fairness in Matroid Allocation Problems (NeurIPS 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.