Efficient Algorithms for Budgeted Profit Maximization With Theoretical Guarantees

Given a social network G = (V,E), the unconstrained profit maximization problem aims to identify a subset S ⊆ V that maximizes the net profit, defined as the expected influence spread Γ(S) of set S minus the associated cost c(S), i.e., Γ(S) − c(S). However, this problem presupposes an unlimited budget, which is often impractical in real scenarios. Motivated by this, we investigate the budgeted profit maximization (BPM) problem by adding a budget constraint. Unfortunately, addressing the BPM problem with a theoretical approximation guarantee remains relatively under-explored in the literature. In response, assuming Γ(S) is known for any S ⊆V,wepropose an algorithm that guarantees returning a set S^o such that (Formula presented),where S∗ denotes an optimal solution for BPM. Then, we develop a practical solution, which uses the reverse reachable set (RR-set) technique for influence estimation, without assuming knowledge of Γ(S), while still maintaining a strong approximation guarantee. Additionally, similar to existing RR-set-based solutions for influence cascade-related problems, our RR-set-based solution relies on generating a large number of random RR-sets to accurately estimate Γ(S). However, the existing RR-set generation method suffers from high memory stall rates due to its irregular memory access patterns, leaving room for further efficiency improvement. Therefore, we propose a new RR-set generation method that utilizes batch execution and cache prefetching. When a memory access is required, instead of stalling while waiting for data, the CPU first issues an asynchronous prefetch request to load the target data into the cache, and then switches to processing the generation of other RR-sets within the same batch, effectively hiding memory access latency. This method can be seamlessly integrated into existing RR-set-based solutions to improve their efficiency. Finally, we conduct extensive experiments on real, large-scale datasets to demonstrate the effectiveness and efficiency of our proposed solutions.