Journal
IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING
Volume 29, Issue 9, Pages 1943-1956Publisher
IEEE COMPUTER SOC
DOI: 10.1109/TKDE.2017.2676771
Keywords
Rejection-aware spatial crowdsourcing; acceptance maximization; greedy algorithm; local search
Categories
Funding
- Hong Kong RGC Project [N_HKUST637/13]
- NSFC Guang Dong Grant [U1301253]
- NSFC [61232018, 61328202]
- National Grand Fundamental Research 973 Program of China [2014CB340303]
- Microsoft Research Asia Gift Grant
Ask authors/readers for more resources
With the rapid development of mobile networks and the widespread usage of mobile devices, spatial crowdsourcing, which refers to assigning location-based tasks to moving workers, has drawn increasing attention. One of the important issues in spatial crowdsourcing is task assignment, which allocates tasks to appropriate workers. However, existing works generally assume that no rejection would happen after the task assignment is completed by the server. Ignorance of such an operation can lead to low system throughput. Thus, in this paper, we take workers' rejection into consideration and try to maximize workers' acceptance in order to improve the system throughput. Specifically, we first formally define the problem of maximizing workers' acceptance in rejection-aware spatial crowdsourcing. Unfortunately, the problem is NP-hard. We propose two exact solutions to obtain the optimal assignment, but they are not efficient enough and not scalable for large inputs. Then, we present four approximation approaches for improving the efficiency. Finally, we show the effectiveness of the proposed pruning strategy for the exact solutions and the superiority of the proposed Greedy algorithm over other approximation methods through extensive experiments.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available