{"ID":2862969,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.26579","arxiv_id":"2509.26579","title":"Efficient Approximation Algorithms for Fair Influence Maximization under Maximin Constraint","abstract":"Fair Influence Maximization (FIM) seeks to mitigate disparities in influence across different groups and has recently garnered increasing attention. A widely adopted notion of fairness in FIM is the maximin constraint, which directly requires maximizing the utility (influenced ratio within a group) of the worst-off group. Despite its intuitive formulation, designing efficient algorithms with strong theoretical guarantees remains challenging, as 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.","short_abstract":"Fair Influence Maximization (FIM) seeks to mitigate disparities in influence across different groups and has recently garnered increasing attention. A widely adopted notion of fairness in FIM is the maximin constraint, which directly requires maximizing the utility (influenced ratio within a group) of the worst-off gro...","url_abs":"https://arxiv.org/abs/2509.26579","url_pdf":"https://arxiv.org/pdf/2509.26579v2","authors":"[\"Xiaobin Rui\",\"Qiangpeng Fang\",\"Chen Peng\",\"Jilong Shi\",\"Zhixiao Wang\",\"Wei Chen\"]","published":"2025-09-30T17:39:27Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}