2018/07/26 by Jiaxu Liu, Jia-Xu Liu, Ke Xu +2
Computer Science · Decision Sciences · #Auction Theory and Applications #Databases (cs.DB) #FOS: Computer and information sciences #Mobile Crowdsensing and Crowdsourcing #Optimization and Search Problems #cs.DB
paper · pdf · doi:10.48550/arxiv.1807.09920
21 pages, 6 figures, 2 tables
arxiv created 2018/07/26 · openalex publication_date 2018/07/26 · arxiv updated 2018/07/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The prevalence of mobile internet techniques stimulates the emergence of various spatial crowdsourcing applications. Certain of the applications serve for requesters, budget providers, who submit a batch of tasks and a fixed budget to platform with the desire to search suitable workers to complete the tasks in maximum quantity. Platform lays stress on optimizing assignment strategies on seeking less budget-consumed worker-task pairs to meet requesters' demands. Existing research on the task assignment with budget constraint mostly focuses on static offline scenarios, where the spatiotemporal information of all workers and tasks is known in advance. However, workers usually appear dynamically on real spatial crowdsourcing platforms, where existing solutions can hardly handle it. In this paper, we formally define a novel problem Budget-aware Online task Assignment(BOA) in spatial crowdsourcing applications. BOA aims to maximize the number of assigned worker- task pairs under a budget constraint where workers appear dynamically on platforms. To address the BOA problem, we first propose an efficient threshold-based greedy algorithm Greedy-RT which utilizes a random generated threshold to prune the pairs with large travel cost. Greedy-RT performs well in adversary model when compared with simple greedy algorithm, but it is unstable in random model for its randomly generated threshold may produce poor quality in matching size. We then propose a revised algorithm Greedy-OT which could learn approximately optimal threshold from historical data, and consequently improves matching size significantly in both models. Finally, we verify the effectiveness and efficiency of the proposed methods through extensive experiments on real and synthetic datasets.