  With the rapid development of mobile devices and crowdsourcing platforms, the
spatial crowdsourcing has attracted much attention from the database community.
Specifically, the spatial crowdsourcing refers to sending location-based
requests to workers, based on their current positions. In this paper, we
consider a spatial crowdsourcing scenario, in which each worker has a set of
qualified skills, whereas each spatial task (e.g., repairing a house,
decorating a room, and performing entertainment shows for a ceremony) is
time-constrained, under the budget constraint, and required a set of skills.
Under this scenario, we will study an important problem, namely multi-skill
spatial crowdsourcing (MS-SC), which finds an optimal worker-and-task
assignment strategy, such that skills between workers and tasks match with each
other, and workers' benefits are maximized under the budget constraint. We
prove that the MS-SC problem is NP-hard and intractable. Therefore, we propose
three effective heuristic approaches, including greedy, g-divide-and-conquer
and cost-model-based adaptive algorithms to get worker-and-task assignments.
Through extensive experiments, we demonstrate the efficiency and effectiveness
of our MS-SC processing approaches on both real and synthetic data sets.
