Efficient Algorithms for Budgeted Profit Maximization With Theoretical Guarantees
- 23 January 2026
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 38 (4) , 2234-2248
Abstract
Given a social network $G=(V, E)$ , the unconstrained profit maximization problem aims to identify a subset $S \subseteq V$ that maximizes the net profit, defined as the expected influence spread $\Gamma (S)$ of set $S$ minus the associated cost $c(S)$ , i.e., $\Gamma (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 $\Gamma (S)$ is known for any $S \subseteq V$ , we propose an algorithm that guarantees returning a set $S^{o}$ such that $\Gamma (S^{o}) - c(S^{o}) \geq (1 - \frac{1}{e}) \frac{\Gamma (S^{*})}{2} - \frac{c(S^{*})}{2}$ , 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 $\Gamma (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 $\Gamma (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.
Keywords
Funding Information
- Hong Kong Research Grants Council (16202722)
- Hong Kong Research Grants Council (16210625)
- Hong Kong Research Grants Council (T43-513/23-N)
- Hong Kong Research Grants Council (T22-607/24N)
- HKUST-WeBank Joint Laboratory (WEB24EG01-N)
- JC STEM Lab of Data Science Foundations funded by The Hong Kong Jockey Club Charities (14217322)
- Tencent Rhino-Bird Focused Research
- Hong Kong Research Grants (PolyU 25201221)
- Hong Kong Research Grants (PolyU 15205224)
- National Natural Science Foundation of China (62202404)
- Postdoc Matching Fund Scheme
- Hong Kong Polytechnic University (1-W33U)
- National Natural Science Foundation of China (62402410)
- Guangdong Provincial Project (2023QN10X025)
This publication has 45 references indexed in Scilit:
- Budget-constrained profit maximization without non-negative objective assumption in social networksJournal of Global Optimization, 2024
- Correction to: Guess Free Maximization of Submodular and Linear SumsAlgorithmica, 2022
- Efficient Approximation Algorithms for Adaptive Target Profit Maximization2020
- Profit Maximization over Social Networks2012
- Defining and Evaluating Network Communities Based on Ground-Truth2012
- A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization2012
- Maximizing non-monotone submodular set functions subject to different constraints: Combined algorithmsOperations Research Letters, 2011
- The Design of Approximation Algorithms2011
- Scalable Influence Maximization in Social Networks under the Linear Threshold Model2010
- Constrained Non-monotone Submodular Maximization: Offline and Secretary Algorithms2010