标题： 在最大化最小约束下的公平影响最大化的高效近似算法 显示英文标题

标题： Efficient Approximation Algorithms for Fair Influence Maximization under Maximin Constraint

摘要： 旨在减少不同群体之间的影响力差异，公平影响力最大化（FIM）最近引起了广泛关注。最大最小约束是FIM问题中采用的一种常见公平性概念，它提出了一个直接且直观的要求，即最不利群体的效用（群体内的影响比例）应被最大化。尽管在最大最小约束下的FIM目标在概念上很简单，但开发具有强理论保证的高效算法仍然是一个开放挑战。困难来自于最大最小目标不满足子模性，这是传统影响力最大化设置中设计近似算法的关键属性。在本文中，我们通过提出一个包含组内最大化（IGM）和组间最大化（AGM）的两步优化框架来解决这一挑战。我们首先证明了任何单个组内的影响力扩散仍保持子模性，从而实现了组内的有效优化。基于此，IGM应用一种贪心方法为每个组选择高质量的种子。在第二步中，AGM通过引入两种策略：均匀选择（US）和贪心选择（GS）来协调组间的种子选择。我们证明当组完全不连通时，AGM-GS对最优解具有$(1 - 1/e - \varepsilon)$的近似，而AGM-US无论组结构如何都能保证大约$\frac{1}{m}(1 - 1/e - \varepsilon)$的下界，其中$m$表示组的数量。 显示英文摘要

摘要： Aiming to reduce disparities of influence across different groups, Fair Influence Maximization (FIM) has recently garnered widespread attention. The maximin constraint, a common notion of fairness adopted in the FIM problem, imposes a direct and intuitive requirement that asks the utility (influenced ratio within a group) of the worst-off group should be maximized. Although the objective of FIM under maximin constraint is conceptually straightforward, the development of efficient algorithms with strong theoretical guarantees remains an open challenge. The difficulty arises from the fact that the maximin objective does not satisfy submodularity, a key property for designing approximate algorithms in traditional influence maximization settings. In this paper, we address this challenge by proposing a two-step optimization framework consisting of Inner-group Maximization (IGM) and Across-group Maximization (AGM). We first prove that the influence spread within any individual group remains submodular, enabling effective optimization within groups. Based on this, IGM applies a greedy approach to pick high-quality seeds for each group. In the second step, AGM coordinates seed selection across groups by introducing two strategies: Uniform Selection (US) and Greedy Selection (GS). We prove that AGM-GS holds a $(1 - 1/e - \varepsilon)$ approximation to the optimal solution when groups are completely disconnected, while AGM-US guarantees a roughly $\frac{1}{m}(1 - 1/e - \varepsilon)$ lower bound regardless of the group structure, with $m$ denoting the number of groups