Research map / Learning theory and algorithms / Fairness
Fair Submodular Cover
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.
Introduces Fair Submodular Cover (FSC), giving discrete and continuous bicriteria algorithms with fairness-balanced solutions, and validates them on fair maximum coverage over a Twitch graph.
Problem
Submodular cover that must return a minimum-size subset satisfying group-proportion fairness constraints over a protected attribute, which prior work (fair submodular maximization) does not address.
Approach
Uses the duality between FSC and fair submodular maximization: converts FSM bicriteria algorithms into FSC algorithms via guessing the optimal size, and builds beta-extensions of fairness matroids so that FSM subroutines can exceed the budget by a factor beta and reach near-full function value; includes discrete greedy/threshold variants and a continuous threshold-greedy with multilinear extension
Key results
- Discrete FSC algorithms achieve (1/ε, 1-O(ε)) bicriteria guarantees, and the continuous algorithm achieves (ln(1/ε), 1-O(ε)), matching unfair submodular cover's best bicriteria ratio.
- On Twitch_5000 with τ=2400, over 80% of users in greedy-bi solutions are English speakers, while the proposed fair algorithms yield significantly fairer language distributions.
- Fair algorithms return solutions of higher cardinality than the unfair greedy baseline, a stated trade-off.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use greedy-fair-bi or threshold-fairness-bi with convert-fair instead of standard greedy-bi | Fair maximum coverage on Twitch_5000 · Twitch_5000 | fairness of language distribution | Helped |
| Use greedy-bi instead of greedy-fair-bi or threshold-fairness-bi | Fair maximum coverage on Twitch_5000 · Twitch_5000, τ = 2400 | English-speaker share: over 80 % | Hurt |
| Enforce fairness using greedy-fair-bi or threshold-fairness-bi instead of standard greedy-bi | Fair maximum coverage on Twitch_5000 · Twitch_5000 | solution cardinality | Hurt |
Limitations
- Bicriteria guarantee: the value constraint f(S)≥τ is met only up to factor 1-O(ε), so solutions are not strictly feasible.
- Fair solutions require larger cardinality than the unfair greedy baseline.
- Continuous algorithm is query-heavy and its guarantee holds in expectation/with probability.
Experimental setup
Datasets: Twitch Gamers subset (Twitch_5000)
Benchmarks: Twitch_5000 fair maximum coverage
Metrics: f value solution cost (size) fairness difference
Baselines: greedy-bi
Builds on: fairness matroid (Halabi et al.) greedy submodular cover (Wolsey) threshold greedy (Badanidiyuru and Vondrak) multilinear extension pipage rounding
Closest papers by meaning
- Improved Algorithms for Fair Matroid Submodular Maximization (NeurIPS 2025 · similarity 0.90)
- An Asymptotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale (ICML 2025 · similarity 0.87)
- A Dynamic Algorithm for Weighted Submodular Cover Problem (ICML 2024 · similarity 0.87)
- On Socially Fair Low-Rank Approximation and Column Subset Selection (NeurIPS 2024 · similarity 0.86)
- Practical $0.385$-Approximation for Submodular Maximization Subject to a Cardinality Constraint (NeurIPS 2024 · similarity 0.86)
- Relax and Merge: A Simple Yet Effective Framework for Solving Fair $k$-Means and $k$-sparse Wasserstein Barycenter Problems (ICLR 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.