Online Dependent Task Assignment in Preference Aware Spatial Crowdsourcing
Online Dependent Task Assignment in Preference Aware Spatial Crowdsourcing
复制标题
DOI：
10.1109/tsc.2022.3217125
复制
发表时间：
2023-07
影响因子：
8.1
通讯作者：
Jiajun Yao;Lei Yang;Xiaohua Xu
中科院分区：
文献类型：
--
作者：
Jiajun Yao;Lei Yang;Xiaohua Xu
空间众包平台在人们的日常生活中越来越受欢迎。空间众包的一个基本问题是任务分配，任务分配是为了满足一定的目标，将空间任务适当地分配给劳动者。以往的研究多集中在实时微任务分配上，没有考虑任务间的依赖关系。为了解决这一问题，本文定义并提出了偏好感知空间众包中的在线依赖任务分配（ODTA）问题。我们首先证明了ODTA是$\mathcal {NP}$NP-hard。然后，我们设计了一种基于阈值的对抗顺序模型算法，得到了竞争比的近最优理论界。更重要的是，考虑到随机订单到达模型，我们进一步提出了基于两阶段框架的三种算法，即ODTA-Greedy、ODTA-Greedy- op和ODTA-OPT，这三种算法在竞争比为$\frac{1}{8}$18、$\frac{1}{8}$18和$\frac{1}{4}$14时更有效。在合成数据集和真实数据集上的实验结果表明，我们提出的ODTA-OPT方法在整体效用方面优于代表性方法。
Spatial crowdsourcing platforms have become increasingly popular in people's daily life. A fundamental problem in spatial crowdsourcing is task assignment, which assigns spatial tasks to the workers appropriately in order to satisfy certain objectives. Previous studies usually focus on the real-time micro-task allocation, which does not consider the dependency relationships among tasks. To address this limitation, in this article, we define and formulate a new problem, called Online Dependent Task Assignment (ODTA) in preference aware spatial crowdsourcing. We first prove that ODTA is $\mathcal {NP}$NP-hard. Then, we design a threshold-based algorithm in the adversarial order model and obtain a near-optimal theoretical bound on the competitive ratio. More importantly, considering the random order arrival model, we further present three algorithms based on a two-stage framework, namely ODTA-Greedy, ODTA-Greedy-OP and ODTA-OPT, which are more effective with a constant competition ratio of $\frac{1}{8}$18, $\frac{1}{8}$18 and $\frac{1}{4}$14, respectively. Experimental results on both synthetic and real datasets show that our proposed ODTA-OPT approach outperforms the representative approaches in terms of overall utility.