Affinitive Diversity-Aware Task Allocation in Spatial Crowdsourcing

With the rapid development of mobile network and devices, spatial crowdsourcing (SC) has recently attracted much attention. For the improvement of quality of service (QoS) in spatial crowdsourcing platforms, existing works usually adopt the many-to-one strategy - assigning multiple workers as a team for each published task. However, such an allocation scheme fails to consider team characteristics which can strongly affect the QoS for some experience-sensitive collaborative tasks. In this paper, we jointly consider two team characteristics to further improve the QoS: Diversity, which is the union of experiences within a team and Affinity, which is how efficiently team members collaborate. Inspired by these two characteristics, we study an important problem, namely, Affinitive Diversity-Aware Spatial Crowdsourcing (ADA-SC), which aims to find an allocation scheme, such that each team satisfies the affinity requirement of the corresponding task and maximizes the team diversity under budget and spatial constraints. Since ADA-SC is proven to be NP-hard by reduction from the set cover problem with nonlinear constraints, we propose two submodular approximation algorithms with pruning strategies for two single-task scenarios. Then a greedy-based algorithm is designed for the multi-task scenario. Extensive experiments on real and synthetic data verify the effectiveness of our proposed methods.