Nonsubmodular constrained profit maximization from increment perspective

Liman Du (), Shengminjie Chen (), Suixiang Gao () and Wenguo Yang ()
Additional contact information
Liman Du: University of Chinese Academy of Science
Shengminjie Chen: University of Chinese Academy of Science
Suixiang Gao: University of Chinese Academy of Science
Wenguo Yang: University of Chinese Academy of Science

Journal of Combinatorial Optimization, 2022, vol. 44, issue 4, No 24, 2598-2625

Abstract: Abstract The growing importance of online social networks where people share information with others leads to the emergence of viral marketing, a new way to promote the sales of products. A derivation of classical Influence Maximization (IM) problem is the Profit Maximization (PM) problem that we focus on in this paper. We propose the PM problem with a cardinality constraint in order to make it closer to the real marketing activities. Without a fixed and pre-determined budget for seed selection, the profit spread metric of PM considers the total benefit and cost. The difference between influence spread metric and profit spread metric is that the latter is no longer monotone and lose the property of submodularity in general. Due to the natural form as the difference between two submodular functions, the profit spread metric admits a DS decomposition. What matters is that we design a Marginal increment-based Prune and Search (MPS) algorithm. From the perspective of marginal increment, MPS algorithm can compute profit spread more directly and accurately. Extensive experiments demonstrate the effectiveness and outperformance of our algorithm.

Keywords: Profit maximization; Nonsubmodularity; Social network (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-021-00774-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:44:y:2022:i:4:d:10.1007_s10878-021-00774-6

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-021-00774-6

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().