| In recent years the computing power of mobile devices has been rapidly developed.At the same time,the cost of equipment is also rapidly declining.Smart mobile devices have touched every corner of our lives.With the development of hardware,more and more mobile crowdsourcing applications are also emerging.In such kind of mobile crowdsourcing problem,the most difficult problem is the task assignment problem,that is,how to assign the tasks in different positions efficiently to the users in the dynamic platform.An efficient task allocation scheme can improve the efficiency of tasks,which can not only improve income of users,but also save cost of platform.In the past articles,due to its complexity,researchers often used heuristic algorithms to solve this task assignment problem,and obtained practical solutions by adjusting parameters.However,these schemes usually only apply some special cases,once the environment changes,the efficiency of the algorithm will be significantly reduced.So we try to get a validated and efficient solution through some combinatorial optimization methods.In this paper,we consider the Bounded Task Allocation Problem(BTAP)in the mobile crowdsourcing platform that deals with the task of spatio-temporal characteristics.We first mathematically model this type of problem into an integer linear programming problem and prove that such problems are NP-hard by reduction.Then we designed an approximation algorithm as a solution.Through rigorous theoretical analysis,we prove that this algorithm is an approximate algorithm with an approximate ratio of(2 + ?)and give an example that the analysis of this approximate ratio is rigorous.Finally,through some simulation experiments,we compared our algorithm with the two previous benchmarks.The experimental results show that our algorithm can also perform well in practical problems.To the best of our knowledge,this article is the first to give a paper with a constant approximation ratio algorithm for the problem. |
PDF Full Text Request