Logarithmic Approximations for Fair k-Set Selection
Authors: Shi Li, Chenyang Xu, Ruilong Zhang
IJCAI 2025 | Venue PDF | Archive PDF | Plain Text | 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. |