An (e-1)/(2e-1)-Approximation Algorithm for Maximizing the Coverage Capability in Vehicle-based Mobile Air Quality Monitoring Systems
Viet Dung Nguyen, Phi Le Nguyen, Trung Hieu Nguyen, Kien Nguyen, Phan Thuan Do
IEEE International Symposium on Network Computing and Applications (NCA 2020), Dec. 2020. [pdf document]

<Abstract>

In this paper, we focus on broadening the monitoring area of a mobile air quality monitoring system, in which the sensors mounted on buses. In particular, we investigate the optimal buses to place the sensors and the optimal monitoring timings to maximize the number of monitored critical regions. We mathematically formulate the targeted problem. Then, we leverage the greedy approach to propose a polynomial-time (e−1)/(2e− 1)-approximation algorithm. We use the data of real bus routes in Hanoi, Vietnam, for the experimentation and show that the proposed algorithm guarantees an average performance ratio of 63.87%.