Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Improved Algorithms for Fair Matroid Submodular Maximization
Authors: Sepideh Mahabadi, Sherry Sarkar, Jakub M Tarnawski
NeurIPS 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our empirical evaluation on a standard suite of real-world datasets clustering, recommendation, and coverage tasks demonstrates the practical effectiveness of our methods. |
| Researcher Affiliation | Collaboration | Sepideh Mahabadi Microsoft Research EMAIL Sherry Sarkar Carnegie Mellon University EMAIL Jakub Tarnawski Microsoft Research EMAIL |
| Pseudocode | No | The paper describes the steps of the algorithm in prose within Section 3 and the proof sketch of Theorem 3.4, but it does not present them in a clearly labeled, structured pseudocode or algorithm block format. |
| Open Source Code | Yes | The code for the paper is available at https://github.com/dj3500/ fair-matroid-submodular-neurips2025. |
| Open Datasets | Yes | We use the Pokec social network [LK14]. ... We use a dataset of 4521 phone calls from a Portuguese bank marketing campaign [MCR14]. ... We simulate a movie recommendation system using the Movielens 1M dataset [HK16]. |
| Dataset Splits | No | The paper describes how data is partitioned into groups based on attributes for fairness constraints (e.g., BMI, age, account balance, movie release date, genre) and how the 'r' factor scales solution size, but it does not specify explicit training, validation, or test dataset splits for model evaluation. |
| Hardware Specification | No | All experiments can be run on commodity hardware (CPU only, single-threaded; we do not report runtimes) and take several hours to finish. |
| Software Dependencies | No | The paper discusses algorithms like the greedy algorithm and local search algorithm but does not list any specific software libraries or tools with version numbers used for implementation or execution. |
| Experiment Setup | Yes | OUR(ε) our algorithm of Theorem 3.4, for a range of settings of ε {0.2, 0.5, 0.8}. To compute a high-value solution Y , we run the natural greedy algorithm, which obtains a 1/3-approximation (Theorem 2.5)... Users are partitioned into four BMI categories (underweight, normal, overweight, obese), with upper bounds |Vi| / |V| r for each group Vi. We also enforce fairness by age, with 7 groups: [1, 10], [11, 17], [18, 25], [26, 35], [36, 45], [46+], no age. We set ℓc = 0.9 |Vc| / |V| r uc = 1.5 |Vc| / |V| r . We use r from 10 to 200. ... Each record e V is represented as xe R7 using 7 numeric features... We impose a partition matroid on account balance, with 5 groups... Each group Vi has upper bound r/5. Fairness is enforced by age, with 6 groups... and bounds ℓc = 0.1r + 2, uc = 0.4r for each c. We use r from 30 to 60. ...The product w u vm estimates user u s rating for movie m. For user u, the monotone submodular utility for a set S of movies is f(S) = α P m M max maxm S v mvm , 0 + (1 α) P m S w u vm, with parameter α = 0.85 balancing coverage and personalized user score... with fairness bounds ℓc = 0.8 |Vc| / |V| r and uc = 1.4 |Vc| / |V| r . We use r from 10 to 200. ... We repeat the randomized algorithms 40 times. |