One Rounding Fits All: Memory-Efficient Approximation Algorithms for Partition-Constrained Influence Maximization
Influence Maximization (IM) problem aims to strategically identify a single set of influential individuals who can influence as many users as possible. It was first introduced in the context of viral marketing, where a company pays a small number of influencers to promote a product or service. Nevertheless, with the proliferation of modern social media platforms such as TikTok, real-world viral marketing scenarios have grown increasingly complex, generally requiring multiple sets of users to participate. To handle these scenarios, Huang et al. [42] recently formulated these problems as a general partition-constrained IM problem (IM-PC) and simultaneously proposed a tight (1-1/e-ε)-approximation RAMP algorithm for IM-PC. Despite its strong theoretical guarantee, RAMP is often hindered by its prohibitive memory overhead, as it must maintain 1/ε intermediate subsets during rounding, and sample inefficiency caused by requiring an additional RR set collection exclusively for solution evaluation. To overcome these limitations, we propose RBwA, a memory-efficient and sample-efficient progressive sampling algorithm for IM-PC. At its core, we utilize rademacher average from statistical learning theory to directly estimate solution quality, thereby eliminating the need for additional validation sets and simultaneously reducing the number of rounding invocations to a single call. Furthermore, we also devise a memory-efficient rounding scheme called BwARound for coverage maximization subroutines, which only requires storing one fractional vector and takes maximal feasible steps rather than tiny ε-increments, thus yielding significant improvements in both space complexity and iteration count over the rounding component AMPRound of RAMP. Finally, extensive experiments on large-scale social networks demonstrate the effectiveness of our proposed RBwA and BwARound.