Several works recently focus on monitoring air quality of critical areas using sensors attached to buses. They aim to monitor the maximum number of critical areas using a limited number of sensors. In practice, we may want to have information for all critical areas. We work on the problem of covering all the areas using the minimum number of sensors in this work. We show that, even when the bus routes are not pre-defined, the problem is NP-hard and is significantly harder than the problem of the previous works. Then, we develop two algorithms for the case that the routes are pre-defined. Those algorithms include a fixed parameter tractability and a 2-approximation algorithm for a special case of the problem. Our experiment results show that, although we usually give the similar number of sensors as the algorithm in the previous works, our algorithms have a shorter computation time than the classical greedy algorithm.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Minimum Target Coverage for Air Quality Monitoring Using Bus Routes


    Beteiligte:


    Erscheinungsdatum :

    01.09.2022


    Format / Umfang :

    493161 byte





    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    Computation of Minimum-Time Vessel Ocean Routes Using Genetic Algorithms

    Wisniewski, B. / Chomski, J. / Nowakowski, M. et al. | British Library Conference Proceedings | 2003


    Disaster Region Coverage Using Drones: Maximum Area Coverage and Minimum Resource Utilisation

    Hafiz Suliman Munawar / Ahmed W.A. Hammad / S. Travis Waller | DOAJ | 2022

    Freier Zugriff


    SYSTEMS, DEVICES, AND METHODS FOR GENERATING VEHICLE ROUTES WITHIN SIGNAL COVERAGE ZONES

    WINKLE DAVID / O'BRIEN JOHN JEREMIAH | Europäisches Patentamt | 2019

    Freier Zugriff