In this paper, we study the classic submodular maximization problem subject to a group equality constraint under both non-adaptive and adaptive settings. It has been shown that the utility function of many machine learning applications, including data summarization, influence maximization in social networks, and personalized recommendation, satisfies the property of submodularity. Hence, maximizing a submodular function subject to various constraints can be found at the heart of many of those applications. On a high level, submodular maximization aims to select a group of most representative items (e.g., data points). However, the design of most existing algorithms does not incorporate the fairness constraint, leading to under- or over-representation of some particular groups. This motivates us to study the submodular maximization problem with group equality, where we aim to select a group of items to maximize a (possibly non-monotone) submodular utility function subject to a group equality constraint. To this end, we develop the first constant-factor approximation algorithm for this problem. The design of our algorithm is robust enough to be extended to solving the submodular maximization problem under a more complicated adaptive setting. Moreover, we further extend our study to incorporating a global cardinality constraint.
翻译:在本文中,我们研究了在非适应性和适应性环境下受群体平等制约的典型亚模块最大化问题,已经表明,许多机器学习应用的实用功能,包括数据总和、影响社交网络中的最大化以及个性化建议,都符合亚模块特性的特性。因此,在很多这些应用中,可以发现,将受各种制约的亚模块功能最大化是许多这些应用的核心。在高层次上,亚模块最大化的目的是选择一组最具代表性的项目(例如,数据点)。然而,大多数现有算法的设计并不包含公平性限制,导致某些特定群体代表不足或过多。这促使我们研究亚模块最大化问题与群体平等,目的是选择一组项目以最大限度地实现(可能非模块化的)亚模块效用功能,但受群体平等制约。为此,我们开发了第一个关于该问题的恒定要素近比值算法。我们的算法设计足够强大,足以解决亚模块最大化问题,在更复杂的适应性设置下,我们进一步扩展了我们的研究范围,以纳入一个更复杂的全球基础性调整。