Budget-Constrained Organization of Influential Social Events

Recently, the proliferation of event-based social services has made it possible for organizing personalized offline events through the users' information shared online. In this paper, we study the budget-constrained influential social event organization problem, where the goal is to select a group of influential users with required features to organize a social event under a budget B. We show that our problem is NP-hard and can be formulated as a submodular maximization problem with mixed packing and covering constraints. We then propose several polynomial time algorithms for our problem with provable approximation ratios, which adopt a novel "surrogate optimization" approach and the method of reverse-reachable set sampling. Compared with some related work that can only handle special cases of our problem but with exponential time complexity, our algorithms are much more efficient, and their superiorities on both the running time and the influence spread are demonstrated through extensive experiments using real social networks.