Cost Minimization and Social Fairness for Spatial Crowdsourcing Tasks

Abstract :

Spatial crowdsourcing is an activity consisting in outsourcing spatial tasks to a community of online, yet on-ground and mobile, workers. A spatial task is characterized by the requirement that workers must move from their current location to a specified location to accomplish the task. We study the assignment of spatial tasks to workers. A sequence of sets of spatial tasks is assigned to workers as they arrive. We want to minimize the cost incurred by the movement of the workers to perform the tasks. In the meanwhile, we are seeking solutions that are socially fair. We discuss the competitiveness in terms of competitive ratio and social fairness of the Work Function Algorithm, the Greedy Algorithm, and the Randomized versions of the Greedy Algorithm to solve this problem. These online algorithms are memory-less and are either inefficient or unfair. In this paper, we devise two Distribution Aware Algorithms that utilize the distribution information of the tasks and that assign tasks to workers on the basis of the learned distribution. With realistic and synthetic datasets, we empirically and comparatively evaluate the performance of the three baseline and two Distribution Aware Algorithms.

Document type :
Conference papers
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal-imt.archives-ouvertes.fr/hal-01700150
Contributor : Admin Télécom Paristech <>
Submitted on : Saturday, February 3, 2018 - 5:06:09 PM
Last modification on : Friday, June 7, 2019 - 11:06:44 AM
Long-term archiving on : Thursday, May 3, 2018 - 2:18:18 PM

File

inproceedings-2016-16048-5.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01700150, version 1

Collections

Citation

Qing Liu, T. Abdessalem, Huayu Wu, Zihong Yuan, Stéphane Bressan. Cost Minimization and Social Fairness for Spatial Crowdsourcing Tasks. The 21st International Conference on Database Systems for Advanced Applications , Apr 2016, Dallas, United States. ⟨hal-01700150⟩

Share

Metrics

Record views

243

Files downloads

150