An(e−1/12e-1)-Approximation Algorithm for Maximizing Coverage Capability in Mobile Air Quality Monitoring Systems

摘要

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 $rac{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%.