With the popularization of smart phones, mobile crowdsourcing emerged and gained growing attention in the recent years. Mobile users are now able to conduct complex tasks with the communication between each other. In this paper, we study the task scheduling problem in the mobile crowdsourcing systems based on the spontaneously formed mobile social networks (MSNs). We introduce two crowdsourcing task scheduling problems under this system model, with one problem aiming to minimize the total cost of some crowdsourcing tasks and the other focusing on minimizing the final completion time of the tasks belonging to the same project. We introduce a unified framework to solve the problems and propose two approximation algorithms for these two problems in the offline versions respectively and prove Their approximation ratios accordingly. Based on the two algorithms, we further design two online algorithms to deal with the workers' dynamism and also analyze their competitive ratios. Finally, we verify the effectiveness and efficiency of the proposed methods through numerical experiments on real and synthetic datasets.

Spatial crowdsourcing is an increasingly popular category in the era of mobile Internet and sharing economy, where tasks have spatio-temporal constraints and must be completed at specific locations. In this paper, we focus ontheMulti-ObjectiveSpatio-Temporal task assignment (MOST) problemconsidering the worker heterogeneity in spatial crowdsourcing and model it as a combinatorial multi-objective optimization (MOO) problem with the goals of maximizing the overall task completion rate and minimizing the average task time cost. Finding the optimal global assignment turns out to be intractable since it does not simply imply optimality for an individual worker, as a typical nearest-neighbor heuristic generally does not render a satisfactory result. We prove that the problem is NP-hard. Subsequently, we formulate an efficient algorithm for the MOST problem —Task Clustering basedMixedPriority Queue Scheduling (TAMP). First, we improve the spectral clustering algorithm to evenly divide the task network into different subdomains according to tasks' geographical locations, considering the task clustering phenomena in real scenarios. We then design a mixed priority queue strategy considering the geographical influence and temporal urgency, to schedule workers finishing tasks in sequence. Experiments on synthetic and real datasets demonstrate the efficiency of our solution over other methods.

Spatial crowdsourcing, a human-centric compelling paradigm in performing spatial tasks, has drawn rising attention. Task assignment is of paramount importance in spatial crowdsourcing. Existing studies often use heuristics of various kinds to solve task assignment problems. These schemes usually only apply some specific cases, once the environment changes, the efficiency of the algorithms is significantly reduced. In this paper, we first introduce a taxonomy of task assignment in spatial crowdsourcing. Next, we design an approximation algorithm and get an efficient solution for the important problem, namely, Bounded and Heterogeneous Task Assignment (BHTA), such that the sum of the rewards of workers is maximized subject to multiple constraints. We prove that the BHTA problem is NP-hard. Subsequently, we propose a constant-ratio approximation algorithm based on partition and shifting method to achieve the assignment solution. To meet with the workers' dynamism, we further devise a greedy algorithm and provide theoretical guarantee. Experiments on synthetic and real datasets demonstrate the efficiency of our strategy over previous methods. So far as we know, this paper is the first attempt to give a constant-ratio approximation for such task assignment problems 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.