Timely Watchers: Cost-Effective Schedule for Urban Sensor Patrols
Lists
Only you see this
Abstract
Monitoring urban incivility events is a key challenge in urban management, and mobile crowd sensing has become a powerful approach to it. To encourage citizen participation in sensing, effective patrol schedule is important. In this work, we formulate the urban sensing patrol scheduling problem as a reward-to-cost maximization problem with constraints, called the ROCS problem. We then consider solutions for both offline and online scenarios. For the offline ROCS, which has been shown to be NP-hard, we first design an exact algorithm BNT for its special case using a binary search and negative cycle detection technique with complexity \(O(mn\log (R_{max}))\) and then provide a more efficient greedy algorithm for the general version in \(O(n^2\log (R_{max}))\), where m, n are the number of edges, vertices in the tasks graph and \(R_{max}\) is the largest reward-cost ratio for a single task. For the online ROCS, we design a randomized algorithm augmented with predictions. It leverages Gaussian true value estimation for decision-making to handle the uncertainty inherent in the online setting. Finally, we validate the effectiveness of the method through extensive experiments on real urban event datasets.
BibTeX
@inproceedings{zhang2025timely,
author = {Jiale Zhang and Yang Luo and Yunlong Cheng and Leixia Wang and Xiaofeng Gao and Xiaochun Yang and Guihai Chen},
title = {{Timely Watchers: Cost-Effective Schedule for Urban Sensor Patrols}},
booktitle = {WASA},
year = {2025},
doi = {10.1007/978-981-96-8728-2\_34},
}Loading related content...