A Constant-Factor Approximation for Bounded Task Allocation Problem in Crowdsourcing
Shuang Wu, Xiaofeng Gao, Fan Wu, Guihai Chen · 2017
As the technology advances, there are more and more mobile crowdsensing (MCS) platforms that try to leverage these devices to improve the quality of our life. In this paper, we consider a bounded task allocation problem (BTAP) in MCS platforms that involve the time-sensitive and location-dependent tasks. We first formulate the bounded task allocation problem as an integer programing problem and prove its NP-hardness. Then we propose an approximated algorithm to solve the problem with (2+ε)-approximated ratio and show that it is a tight bound. So far as we know, we are the first to give a constant approximated ratio for such task allocation problems. Finally, we make some simulations to show the performance of our scheme comparing with other two benchmarks.