Logarithmic Approximations for Fair k-Set Selection
Preprint
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\cup 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(\frac{\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.
Keywords
All Related Versions
This publication has 22 references indexed in Scilit:
- Maximizing Submodular Functions for Recommendation in the Presence of Biases2023
- Submodular Feature Selection for Partial Label Learning2022
- Fairness in Recommendation Ranking through Pairwise Comparisons2019
- Monotone Submodular Maximization over a Matroid via Non-Oblivious Local SearchSIAM Journal on Computing, 2014
- Submodular Approximation: Sampling-based Algorithms and Lower BoundsSIAM Journal on Computing, 2011
- Maximizing a Monotone Submodular Function Subject to a Matroid ConstraintSIAM Journal on Computing, 2011
- Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures2010
- A note on maximizing a submodular set function subject to a knapsack constraintOperations Research Letters, 2004
- An analysis of approximations for maximizing submodular set functions—IMathematical Programming, 1978
- The Rectilinear Steiner Tree Problem is $NP$-CompleteSIAM Journal on Applied Mathematics, 1977