Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2022.49
URN: urn:nbn:de:0030-drops-173343
URL: https://drops.dagstuhl.de/opus/volltexte/2022/17334/
Erlebach, Thomas ; Luo, Kelin ; Spieksma, Frits C.R.
Package Delivery Using Drones with Restricted Movement Areas
| pdf-format: |
|
Abstract
For the problem of delivering a package from a source node to a destination node in a graph using a set of drones, we study the setting where the movements of each drone are restricted to a certain subgraph of the given graph. We consider the objectives of minimizing the delivery time (problem DDT) and of minimizing the total energy consumption (problem DDC). For general graphs, we show a strong inapproximability result and a matching approximation algorithm for DDT as well as NP-hardness and a 2-approximation algorithm for DDC. For the special case of a path, we show that DDT is NP-hard if the drones have different speeds. For trees, we give optimal algorithms under the assumption that all drones have the same speed or the same energy consumption rate. The results for trees extend to arbitrary graphs if the subgraph of each drone is isometric.
BibTeX - Entry
@InProceedings{erlebach_et_al:LIPIcs.ISAAC.2022.49,
author = {Erlebach, Thomas and Luo, Kelin and Spieksma, Frits C.R.},
title = {{Package Delivery Using Drones with Restricted Movement Areas}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {49:1--49:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17334},
URN = {urn:nbn:de:0030-drops-173343},
doi = {10.4230/LIPIcs.ISAAC.2022.49},
annote = {Keywords: Mobile agents, approximation algorithm, inapproximability}
}
| Keywords: | Mobile agents, approximation algorithm, inapproximability | |
| Seminar: | 33rd International Symposium on Algorithms and Computation (ISAAC 2022) | |
| Issue date: | 2022 | |
| Date of publication: | 14.12.2022 |
