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..
Fair Matroid Selection
Authors: Kiarash Banihashem, MohammadTaghi Hajiaghayi, Danny Mittal
NeurIPS 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We investigate the problem of sequentially selecting elements of an unknown matroid in an online manner to form an independent set, with the goal of maximizing the minimum probability of acceptance across all elements, a property we define as f-fairness. Under adversarial arrival orders, we design an α(ln k + 1)-fair algorithm, where α is the arboricity of the matroid and k is the rank, a result that is nearly optimal. For laminar matroids, we develop a (2α 1)-fair algorithm, which is optimal up to constant factors, achieved through a novel online coloring scheme. In the random arrival order setting, we achieve a (4 + o(1))α-fair algorithm for graphic matroids, matching the optimal result up to constant factors, relying on a novel technique for learning a degeneracy ordering using a sampled subset of edges. We further generalize our result to p-matchoids, obtaining a β(p ln k + 1)-fair algorithm for the adversarial arrival model, where β is the optimal offline fairness. Notably, all our results can be extended to a setting with no prior knowledge of the matroid with only a logarithmic increase in the fairness factor. |
| Researcher Affiliation | Academia | Kiarash Banihashem Department of Computer Science University of Maryland EMAIL Mohammad Taghi Hajiaghayi Department of Computer Science University of Maryland EMAIL Danny Mittal Department of Computer Science University of Maryland EMAIL |
| Pseudocode | Yes | Algorithm 1: General algorithm for adversarial order fair matroid selection. Let m = α(ln k + 1) . For each j = 1, . . . , m, initialize the set Aj as empty. Choose r uniformly at random from 1, . . . , m. for e being presented do Let j be the minimum among 1, . . . , m such that Aj {e} is independent. Insert e into Aj. if j = r then |
| Open Source Code | No | The paper is theoretical and does not contain any experiments. The NeurIPS Paper Checklist for 'Open access to data and code' states 'NA' with the justification: 'The paper is theoretical and does not contain any experiments.' |
| Open Datasets | No | The paper is theoretical and does not contain any experiments. The NeurIPS Paper Checklist for 'Open access to data and code' states 'NA' with the justification: 'The paper is theoretical and does not contain any experiments.' |
| Dataset Splits | No | The paper is theoretical and does not involve empirical evaluation on datasets, thus there is no mention of dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not contain any experiments, therefore no hardware specifications are provided. |
| Software Dependencies | No | The paper is theoretical and does not contain any experiments, therefore no software dependencies with version numbers are listed. |
| Experiment Setup | No | The paper is theoretical and does not describe any experimental setups, hyperparameters, or system-level training settings. |