Logarithmic Approximations for Fair k-Set Selection

2025/05/17 by Shi Li, Chenyang Xu, Li, Shi +3
Business, Management and Accounting · Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Facility Location and Emergency Management #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.2505.12123

openalex publication_date 2025/05/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study the fair k-set selection problem where we aim to select k sets from a given set system such that the (weighted) occurrence times that each element appears in these k selected sets are balanced, i.e., the maximum (weighted) occurrence times are minimized. By observing that a set system can be formulated into a bipartite graph G:=(L∪ R, E), our problem is equivalent to selecting k vertices from R such that the maximum total weight of selected neighbors of vertices in L is minimized. The problem arises in a wide range of applications in various fields, such as machine learning, artificial intelligence, and operations research. 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 a dependent rounding algorithm achieves 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. Finally, we extend all our algorithms to the weighted case and prove that all approximations are preserved.

Citations

• Subset Selection Based On Multiple Rankings in the Presence of Bias: Effectiveness of Fairness Constraints for Multiwinner Voting Score Functions
• Polylogarithmic Approximation for Robust s-t Path
• Maximizing Submodular Functions for Recommendation in the Presence of Biases
• Provable Data Subset Selection For Efficient Neural Network Training
• Host Community Respecting Refugee Housing
• A Survey on the Fairness of Recommender Systems
• Training Subset Selection for Weak Supervision
• Random Rank: The One and Only Strategyproof and Proportionally Fair Randomized Facility Location Mechanism
• Fairness in Recommendation: Foundations, Methods and Applications
• Fast Feature Selection with Fairness Constraints
• Strategyproof Mechanisms For Group-Fair Facility Location Problems
• Causal Feature Selection for Algorithmic Fairness
• Multi-stakeholder Recommendation and its Connection to Multi-sided\n Fairness
• Fairness in Recommendation Ranking through Pairwise Comparisons
• Fast Best Subset Selection: Coordinate Descent and Local Combinatorial\n Optimization Algorithms
• Subset Selection with Shrinkage: Sparse Linear Modeling when the SNR is low
• A Tight Combinatorial Algorithm for Submodular Maximization Subject to a Matroid Constraint
• Monotone Submodular Maximization over a Matroid via Non-Oblivious Local Search
• Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
• A constructive proof of the general Lovasz Local Lemma
• Submodular approximation: sampling-based algorithms and lower bounds
• An analysis of approximations for maximizing submodular set functions—I

Related

• Proportionally Fair Matching via Randomized Rounding
• Approximation in (Poly-) Logarithmic Space
• O(log n)-Approximation Algorithms for Bipartiteness Ratio
• Structural Rounding: Approximation Algorithms for Graphs Near an Algorithmically Tractable Class
• Quick-Sort Style Approximation Algorithms for Generalizations of Feedback Vertex Set in Tournaments