Notice: This website is continuously updated as new conference proceedings and journal volumes are published. Consequently, the figures presented here may differ from those reported in our publications.
A brief overview of our methodology is provided on the Methods page, along with references to publications documenting our approach and links to the code and data used in each study.
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.
Improved Algorithms for Fair Matroid Submodular Maximization
Authors: Sepideh Mahabadi, Sherry Sarkar, Jakub M Tarnawski
NeurIPS 2025 | Venue PDF | LLM Run Details | Input Tokens: 20,480 Total number of tokens sent to the LLM as input for this paper's analysis. | Output Tokens: 3,805 Total number of tokens produced by the LLM (including reasoning/thinking tokens) for this paper's analysis.
| 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. |