## תקציר

In this paper we study covering problems that arise in wireless networks with Unmanned Aerial Vehicles (UAVs) swarms. In the general setting we want to place a set of UAVs that should cover a given set of planar users under some constraints and we want to maintain the solution efficiently in a static and dynamic fashion. Specifically, for a set S of n non-negative weighted points in the plane, we consider a set P of m disks (or squares) of radius where the goal is to place (and maintain under dynamic updates) their location such that the sum of the weights of the points in S covered by disks from P is maximized. In the connected version, we also require that the graph imposed on P should be connected. Moreover, for the static connected version we improve the results from[1] and we obtain a constant factor approximation algorithm. In order to solve our problem under various requirements, we use a variety of techniques including dynamic grid, a reduction to Budgeted Subset Steiner Connected Dominating Set problem, tree partition, and others. We present several simple data structures that maintain an O(1)-approximate solution efficiently, under insertions and deletions of points to/from S where each update operation can be performed in logarithmic time.

שפה מקורית | אנגלית |
---|---|

כותר פרסום המארח | Algorithms for Sensor Systems - 16th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2020, Revised Selected Papers |

עורכים | Cristina M. Pinotti, Alfredo Navarra, Amitabha Bagchi |

מוציא לאור | Springer Science and Business Media Deutschland GmbH |

עמודים | 32-44 |

מספר עמודים | 13 |

מסת"ב (מודפס) | 9783030624002 |

מזהי עצם דיגיטלי (DOIs) | |

סטטוס פרסום | פורסם - 2020 |

אירוע | 16th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2020 - Pisa, איטליה משך הזמן: 9 ספט׳ 2020 → 10 ספט׳ 2020 |

### סדרות פרסומים

שם | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

כרך | 12503 LNCS |

ISSN (מודפס) | 0302-9743 |

ISSN (אלקטרוני) | 1611-3349 |

### כנס

כנס | 16th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2020 |
---|---|

מדינה/אזור | איטליה |

עיר | Pisa |

תקופה | 9/09/20 → 10/09/20 |

### הערה ביבליוגרפית

Publisher Copyright:© 2020, Springer Nature Switzerland AG.