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..
Logarithmic Approximations for Fair k-Set Selection
Authors: Shi Li, Chenyang Xu, Ruilong Zhang
IJCAI 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We first prove that the problem is NP-hard even if the maximum degree of the input bipartite graph is 3, and the problem is in P when = 2. We then show that the problem is also in P when the input set system forms a laminar family. Based on intuitive linear programming, we show that two rounding algorithms achieve O( log n log log n)-approximation on general bipartite graphs, and an independent rounding algorithm achieves O(log )-approximation on bipartite graphs with a maximum degree . We demonstrate that our analysis is almost tight by providing a hard instance for this linear programming. |
| Researcher Affiliation | Academia | Shi Li1 , Chenyang Xu2 and Ruilong Zhang3 1School of Computer Science, Nanjing University, Nanjing, China 2 Software Engineering Institute, East China Normal University, Shanghai, China 3Department of Mathematics, Technical University of Munich, Munich, Germany EMAIL, EMAIL, EMAIL |
| Pseudocode | Yes | Algorithm 1 Independent Rounding Algorithm. Input: The fractional solution x . Output: A set of vertices S R with |S| k with high probability. 1: A { v R : x v ln ln n 10 ln n }; 2: B { v R : x v < ln ln n 10 ln n }; B . 3: if P v B x v 1 then 4: B { u }; u is an arbitrary vertex in B. 5: end if 6: if P v B x v > 1 then 7: for each v B do 8: pv 10 ln n ln ln n x v. Note that pv 1. 9: Independently add v to B with probability pv. 10: end for 11: end if 12: return S A B . Algorithm 2 Algorithm for Degree Bounded Graphs Input: The bipartite graph G := (L R, E); The maximum degree of G; The demand k; The optimal fractional solution x = (x v)v R. Output: A vertex set S R with |S| k. 1: for each vertex v R do 2: pv min{1, (x v + 1 ) 4 ln(2e 2)}. 3: end for 4: S1 { v R | pv = 1 }; Phase 1 5: if |S1| k then 6: return S S1. 7: end if 8: if |S1| < k then Phase 2 9: for each vertex v R \ S1 do 10: Define Xv { 0, 1 } s.t. Pr[Xv = 1] = pv. 11: end for 12: X { Xv }v R\S1. 13: X Local Search(X, A B). Definition 1 14: S2 { v R \ S1 | Xv = 1 in X }. 15: end if 16: if |S1| + |S2| k then 17: return S S1 S2. 18: end if 19: if |S1| + |S2| < k then Phase 3 20: Pick an arbitrary vertex v from R \ (S1 S2). 21: return S S1 S2 { v }. 22: end if |
| Open Source Code | No | The paper does not provide any explicit statement about releasing code or a link to a source code repository. It refers to a 'full version' in [Li et al., 2025] but does not indicate code availability for the current work. |
| Open Datasets | No | The paper focuses on theoretical algorithms and proofs for the fair k-set selection problem. It discusses conceptual applications but does not use any specific datasets for empirical evaluation, hence no information on open datasets is provided. |
| Dataset Splits | No | The paper is theoretical and does not involve experimental evaluation using datasets, therefore, no dataset splits are mentioned. |
| Hardware Specification | No | The paper is theoretical, presenting mathematical proofs and algorithms. It does not include any experimental results, and thus, no hardware specifications are mentioned. |
| Software Dependencies | No | The paper describes theoretical algorithms and complexity analysis. It does not mention any specific software or library versions used for implementation or experimentation. |
| Experiment Setup | No | The paper is theoretical, focusing on algorithmic design, complexity analysis, and approximation ratios. It does not describe any empirical experiments, hyperparameters, or training configurations. |