Conflict-aware event-participant arrangement

With the rapid development of Web 2.0 and Online To Offline (O2O) marketing model, various online event-based social networks (EBSNs), such as Meetup and Whova, are getting popular. An important task of EBSNs is to facilitate the most satisfactory event-participant arrangement for both sides, i.e. events enroll more participants and participants are arranged with personally interesting events. Existing approaches usually focus on the arrangement of each single event to a set of potential users, and ignore the conflicts between different events, which leads to infeasible or redundant arrangements. In this paper, to address the shortcomings of existing approaches, we first identify a more general and useful event-participant arrangement problem, called Global Event-participant Arrangement with Conflict and Capacity (GEACC) problem, focusing on the conflicts of different events and making event-participant arrangements in a global view. Though it is useful, unfortunately, we find that the GEACC problem is NP-hard due to the conflict constraints among events. Thus, we design two approximation algorithms with provable approximation ratios and an exact algorithm with pruning technique to address this problem. Finally, we verify the effectiveness and efficiency of the proposed methods through extensive experiments on real and synthetic datasets.