Résumé: Mobile crowd sourcing (MCS) has grown to be a powerful computation paradigm to harness human power to solve real-world problems. Many commercial MCS platforms have arisen, enabling various novel applications. As crowd workers can be unreliable, a critical issue of these platforms is quality control. Many task assignment approaches have been proposed to increase the quality of crowd sourced tasks by matching workers and tasks in a bipartite graph. However, they fail to apply to MCS platforms where tasks are bound with locations. This paper considers the quality-aware online task assignment problem with location-based tasks. The goal is to optimize tasks' overall quality by assigning appropriate sets of tasks to workers in an online manner. To solve this problem, we propose a probabilistic quality measurement model and a hitchhiking model to characterize workers' behavior. Then we design a polynomial-time online assignment algorithm and prove that the proposed algorithm approximates the offline optimal solution with a competitive ratio of 10/7. Through extensive simulations, we demonstrate the efficiency and effectiveness of our solution.

Langue: Anglais