Improved Streaming Fair Submodular Maximization under a Knapsack Constraint: Application to Budgeted Fair Influence Maximization

Given a ground set $N$ partitioned into groups $G_1,\dots ,G_h$, we seek a subset $S\subseteq N$ maximizing a monotone submodular function $f(S)$, subject to a knapsack constraint ${\sum }_{e\in S}{w}_e\le B$ and fairness constraints ${\ell }_i\le |S\cap G_i|\le u_i$ for every group $i$, with particular focus on the streaming setting. This problem arises in many applications, such as budgeted fair influence maximization in social networks. We propose an operation-based reduction method which yields a $0.387-O(\epsilon )$ approximation, improving the previous best guarantee 0.241 in Zhou et al. (2026). Moreover, we give the first constant-factor streaming approximations that satisfy both the knapsack constraint and all fairness constraints exactly. The previous best streaming result (Cui et al., 2024) achieves an approximation ratio of $1/12-O(\epsilon )$ while relaxing each fairness lower bound to $\lfloor {\ell }_i/2\rfloor$. Our two-pass algorithm improves the ratio to $1/(7+\epsilon )$ using $O(K)$ memory, where $K={\sum }_i{u}_i$. We further propose a new technique called density-truncated local search, which achieves a $1/(5+\epsilon )$ approximation using $O(1/\epsilon )$ passes and ${\tilde{O}}_{\epsilon }(K)$ memory. Experiments on budgeted fair influence maximization over real-world social networks show that our algorithms maintain exact feasibility in all runs while achieving competitive influence spread. Additional evaluations show that our algorithms retain over 96% of the influence spread that can be achieved by a greedy method without considering fairness.