{"ID":2885607,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.04159","arxiv_id":"2508.04159","title":"Approximation Algorithms for Scheduling Crowdsourcing Tasks in Mobile Social Networks","abstract":"This paper addresses the scheduling problem in mobile social networks. We begin by proving that the approximation ratio analysis presented in the paper by Zhang \\textit{et al.} (IEEE Transactions on Mobile Computing, 2025) is incorrect, and we provide the correct analysis results. Furthermore, when the required service time for a task exceeds the total contact time between the requester and the crowd worker, we demonstrate that the approximation ratio of the Largest-Ratio-First task scheduling algorithm can reach $2 - \\frac{1}{m}$. Next, we introduce a randomized approximation algorithm to minimize mobile social networks' total weighted completion time. This algorithm achieves an expected approximation ratio of $1.5 + ε$ for $ε\u003e0$. Finally, we present a deterministic approximation algorithm that minimizes mobile social networks' total weighted completion time. This deterministic algorithm achieves an approximation ratio of $\\max\\left\\{2.5,1+ε\\right\\}$ for $ε\u003e0$. Additionally, when the task's required service time or the total contact time between the requester and the crowd worker is sufficiently large, this algorithm can reach an approximation ratio of $1.5+ε$ for $ε\u003e0$.","short_abstract":"This paper addresses the scheduling problem in mobile social networks. We begin by proving that the approximation ratio analysis presented in the paper by Zhang \\textit{et al.} (IEEE Transactions on Mobile Computing, 2025) is incorrect, and we provide the correct analysis results. Furthermore, when the required service...","url_abs":"https://arxiv.org/abs/2508.04159","url_pdf":"https://arxiv.org/pdf/2508.04159v2","authors":"[\"Chi-Yeh Chen\"]","published":"2025-08-06T07:33:27Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}