Fair Representation in Submodular Subset Selection: A Pareto Optimization Approach

In this paper, we study a novel multi-objective combinatorial optimization problem called Submodular Maximization with Fair Representation (SMFR), which selects subsets of bounded costs from a ground set such that a submodular (utility) function $f$ is maximized while a set of $d$ submodular (representativeness) functions $g_1, \ldots, g_d$ are also maximized.SMFR can find applications in machine learning problems where utility and representativeness objectives should be considered simultaneously, such as social advertising, recommendation, and feature selection.We show that the maximization of $f$ and $g_1, \ldots, g_d$ might conflict with each other, so that no single solution can approximate all of them at the same time.Therefore, we propose a Pareto optimization approach to SMFR, which finds a set of solutions to approximate all Pareto optimal solutions with different trade-offs between these objectives.Specifically, it converts an instance of SMFR into several submodular cover instances by adjusting the weights of objective functions and provides approximate solutions by running the greedy algorithm on each submodular cover instance.Finally, we demonstrate the effectiveness of SMFR and our proposed approach in a real-world problem.