Competitive analysis

Epistemology

Algorithm

Optics

Physics

Mathematical optimization

Engineering

Mathematical analysis

World Wide Web

Optimization problem

Philosophy

Artificial intelligence

Heuristic

Focus (optics)

Generalized assignment problem

Online algorithm

Systems engineering

Quality (philosophy)

Task (project management)

Mathematics

Computer science

Embedding

Greedy algorithm

Crowdsourcing

Upper and lower bounds

Assignment problem

Spatial crowdsourcing services, such as Uber and Grabhub, become popular recently. Task assignment plays an important role in offering high-quality services. However, most of the existing solutions for task assignment only focus on the entire performance of the platform and do not optimize the maximum assignment delay. As a result, they cannot handle some real world scenarios which require minimizing the maximum delay in task assignment. In this paper, we study the minimizing maximum delay spatial crowdsourcing (MMD-SC) problem and propose solutions aiming at achieving a worst case controlled task assignment. The MMD-SC problem assumes that both workers and requesters come dynamically and considers not only the workers' travel costs but also the buffering time of tasks, thus it is very challenging due to two-sided online setting. To address these challenges, in this work, we propose a space embedding based online random algorithm with a competitive ratio of O(log n) and two efficient heuristic algorithms, namely the threshold based greedy approach and the batch-based approach. In addition, we demonstrate the effectiveness and efficiency of our methods via extensive experiments on both synthetic and real datasets.

Minimizing Maximum Delay of Task Assignment in Spatial Crowdsourcing