Non-Rejection Aware Online Task Assignment in Spatial Crowdsourcing
Non-Rejection Aware Online Task Assignment in Spatial Crowdsourcing
复制标题
DOI：
10.1109/tsc.2023.3327858
复制
发表时间：
2023-11
影响因子：
8.1
通讯作者：
J. Yao;Lei Yang;Zhenyu Wang;Xiaohua Xu
中科院分区：
文献类型：
--
作者：
J. Yao;Lei Yang;Zhenyu Wang;Xiaohua Xu
Spatial crowdsourcing as a promising computing paradigm has received significant attention recently. A fundamental issue of spatial crowdsourcing is online task assignment, i.e., the platform must make decisions immediately (assign or reject) for newly arriving objects (tasks or workers). Previous studies mostly focus on the rejection-aware assignment, which rarely considers non-rejection assignment for new arrival objects. To solve this new allocation model, in this paper, we first formulate a novel problem, namely Online Non-rejection aware Task Assignment (ONRTA) in spatial crowdsourcing, where an object cannot be rejected by the platform as long as there is a neighbor that satisfies the matching constraint with it. Then, we develop a non-rejection threshold-based random algorithm ONRTA-RT under the adversarial order model while obtaining a theoretical bound on the competitive ratio. More importantly, we consider a more natural random order model and propose a two-stage-based non-rejection aware task assignment approach, ONRTA-Base, which achieves a competitive ratio of $\frac{1}{4}$14. Based on this framework, we further devise two non-rejection assignment approaches, ONRTA-OP and ONRTA-Greedy, which are more effective and run faster with a competitive ratio of $\frac{1}{4}$14 and $\frac{1}{8}$18, respectively. Finally, experiments on synthetic and real datasets demonstrate that our proposed methods outperform the representative methods.
