Logarithmic Approximations for Fair k-Set Selection

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 $\hat{I}”$ of the input bipartite graph is $3$, and the problem is in P when $\hat{I}”=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 \hat{I}”)$-approximation on bipartite graphs with a maximum degree $\hat{I}”$. 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.

To appear in IJCAI 2025