2015 · 43 citations · 25 references
ComputingComputer SystemsMobile ComputingMobile SystemsSchedulingAssignment ProblemsOnline AlgorithmsOnline SchedulingTask SchedulingCompetitive RatioCrowdsourcingOnline Assignment ProblemOnline Bipartite MatchingOnline Task AllocationPolynomial-time AlgorithmsTask Assignment
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.
25
Prashanth Mohan, Venkata N. Padmanabhan, Ramachandran Ramjee · 2008 · 1.3K citations · Full text
Dejun Yang, Guoliang Xue, Xi Fang et al. · 2012 · 1K citations
Zheng Yang, Chenshu Wu, Yunhao Liu · 2012 · 749 citations
Leyla Kazemi, Cyrus Shahabi · 2012 · 500 citations
Social Sciences, Human Geography, Geographic Information Science +6