Coverage and workload cost balancing in spatial crowdsourcing
Ning Wang, Jie Wu, Pouya Ostovari · 2017
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.