An Approximation Algorithm for Bounded Task Assignment Problem in Spatial Crowdsourcing

作     者：Bhatti, Shahzad Sarwar Fan, Jiahao Wang, Kangrui Gao, Xiaofeng Wu, Fan Chen, Guihai 

作者机构：Shanghai Jiao Tong Univ Shanghai Key Lab Scalable Comp & Syst Dept Comp Sci & Engn Shanghai 200240 Peoples R China 

出 版 物：《IEEE TRANSACTIONS ON MOBILE COMPUTING》 (IEEE移动计算汇刊)

年 卷 期：2021年第20卷第8期

页      面：2536-2549页

核心收录：

学科分类：0810[工学-信息与通信工程] 0808[工学-电气工程] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Key R&D Program of China [2019YFB2102200] National Natural Science Foundation of China [61872238, 61972254, 61672353] Shanghai Science and Technology Fund CCF-Huawei Database System Innovation Research Plan [CCF-Huawei DBIR2019002A] Huawei Innovation Research Program [HO2018085286] State Key Laboratory of Air Traffic Management System and Technology [SKLATM20180X] Tencent SocialAds Rhino-Bird Focused Research Program 

主　　题：Task analysis Crowdsourcing Dynamic scheduling Processor scheduling Approximation algorithms Heuristic algorithms Spatial crowdsourcing task assignment matching and scheduling constant-ratio approximation multi-user dynamism 

摘      要：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.