.png){kind=icon}
.png){kind=icon}
Return
An Approximation Algorithm for Bounded Task Assignment Problem in Spatial Crowdsourcing
.png){kind=icon}
PRE
AI
DOI：10.1109/TMC.2020.2984380.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
Task analysis
Crowdsourcing
Dynamic scheduling
Processor scheduling
Approximation algorithms
Heuristic algorithms
Spatial crowdsourcing
task assignment
matching and scheduling
constant-ratio approximation
multi-user dynamism
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
9.2
Papers:
5.6K
Citations:
1.8W