TY - GEN
T1 - Coverage and workload cost balancing in spatial crowdsourcing
AU - Wang, Ning
AU - Wu, Jie
AU - Ostovari, Pouya
N1 - Publisher Copyright:
© 2017 IEEE.
PY - 2018/6/26
Y1 - 2018/6/26
N2 - This paper addresses the coverage and workload-balancing requirements of worker recruiting in spatial crowdsourcing. That is, the recruited workers should be able to visit all the crowdsourcing locations to satisfy a certain quality, e.g., traffic monitoring or climate forecast. In addition, each crowdsourcing operation has a cost, e.g., data traffic or energy consumption, and each crowdsourcing location might have a crowdsourcing budget for the visited workers. The objective of this paper is to find a worker recruiting algorithm, which ensures the coverage requirement and minimizes the maximal crowdsourcing cost for any crowdsourcing location. We gradually discuss the problem from the 1-D scenario to the general 2-D scenario. In the 1-D scenario, we propose a bounded directional greedy algorithm first. Then, we propose a PTAS extension. A dynamic programming solution is further proposed with a higher computation complexity. In the 2-D scenario, we propose a randomized rounding algorithm with an O(log n/log log n) approximation ratio in a high probability. Extensive experiments on realistic traces demonstrate the effectiveness of the proposed algorithms.
AB - This paper addresses the coverage and workload-balancing requirements of worker recruiting in spatial crowdsourcing. That is, the recruited workers should be able to visit all the crowdsourcing locations to satisfy a certain quality, e.g., traffic monitoring or climate forecast. In addition, each crowdsourcing operation has a cost, e.g., data traffic or energy consumption, and each crowdsourcing location might have a crowdsourcing budget for the visited workers. The objective of this paper is to find a worker recruiting algorithm, which ensures the coverage requirement and minimizes the maximal crowdsourcing cost for any crowdsourcing location. We gradually discuss the problem from the 1-D scenario to the general 2-D scenario. In the 1-D scenario, we propose a bounded directional greedy algorithm first. Then, we propose a PTAS extension. A dynamic programming solution is further proposed with a higher computation complexity. In the 2-D scenario, we propose a randomized rounding algorithm with an O(log n/log log n) approximation ratio in a high probability. Extensive experiments on realistic traces demonstrate the effectiveness of the proposed algorithms.
UR - https://www.scopus.com/pages/publications/85050237792
UR - https://www.scopus.com/pages/publications/85050237792#tab=citedBy
U2 - 10.1109/UIC-ATC.2017.8397518
DO - 10.1109/UIC-ATC.2017.8397518
M3 - Conference contribution
AN - SCOPUS:85050237792
T3 - 2017 IEEE SmartWorld Ubiquitous Intelligence and Computing, Advanced and Trusted Computed, Scalable Computing and Communications, Cloud and Big Data Computing, Internet of People and Smart City Innovation, SmartWorld/SCALCOM/UIC/ATC/CBDCom/IOP/SCI 2017 - Conference Proceedings
SP - 1
EP - 8
BT - 2017 IEEE SmartWorld Ubiquitous Intelligence and Computing, Advanced and Trusted Computed, Scalable Computing and Communications, Cloud and Big Data Computing, Internet of People and Smart City Innovation, SmartWorld/SCALCOM/UIC/ATC/CBDCom/IOP/SCI 2017 - Conference Proceedings
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2017 IEEE SmartWorld Ubiquitous Intelligence and Computing, Advanced and Trusted Computed, Scalable Computing and Communications, Cloud and Big Data Computing, Internet of People and Smart City Innovation, SmartWorld/SCALCOM/UIC/ATC/CBDCom/IOP/SCI 2017
Y2 - 4 April 2017 through 8 April 2017
ER -