arXiv:2603.26129 · v2
Improved Algorithms for Unrelated Crowd Worker Scheduling in Mobile Social Networks
摘要
This paper studies task scheduling with unrelated crowd workers in mobile social networks, where the service time of a task depends on the crowd worker that performs it, and the objective is to minimize the total weighted completion time. For identical crowd workers, we tighten the approximation ratio of the Largest-Ratio-First (LRF) algorithm and update the competitive ratio of its online version. For unrelated crowd workers, we show that the time-indexed rounding framework of Im and Li remains valid when worker-dependent contact delays are added, which yields a randomized algorithm with an expected approximation ratio of 1.45; this improves upon the expected ratio of $1.5+ε$ obtained in our previous work for identical crowd workers. We also derandomize this algorithm. To improve computational efficiency, we further propose an algorithm that exploits the optimality of the Smith-ratio order on a single crowd worker, and we prove that it is a deterministic 1.5-approximation algorithm and that its polynomial-time version achieves an approximation ratio arbitrarily close to 1.5. Experiments on synthetic instances and on instances derived from real contact traces show that this algorithm outperforms three variants of LRF in all tested settings, with the largest advantage when the crowd workers are highly heterogeneous, performs on par with a local-search heuristic for unrelated machines, and is within 0.4\% of the optimum on average on small instances that can be solved exactly.
作者备注：36 pages, 8 figures. v2: substantially revised. Clarified the communication model; corrected the LRF and 1.45-approximation analyses; proved that EDTS is a deterministic 1.5-approximation and added a polynomial-time (1.5+eps/2) version; redid all experiments with new baselines, optimal solutions on small instances, and running times. Submitted to the IEEE for possible publication