An Effective Marketing Strategy for Revenue Maximization with a Quantity Constraint

Recently the influence maximization problem has received much attention for its applications on viral marketing and product promotions. However, such influence maximization problems have not taken into account the monetary effect on the purchasing decision of individuals. To fulfill this gap, in this paper, we aim for maximizing the revenue by considering the quantity constraint on the promoted commodity. For this problem, we not only identify a proper small group of individuals as seeds for promotion but also determine the pricing of the commodity. To tackle the revenue maximization problem, we first introduce a strategic searching algorithm, referred to as Algorithm PRUB, which is able to derive the optimal solutions. After that, we further modify PRUB to propose a heuristic, Algorithm PRUB+IF, for obtaining feasible solutions more effciently on larger instances. Experiments on real social networks with different valuation distributions demonstrate the effectiveness of PRUB and PRUB+IF.