2023/06/17 by Anupam, Sagnik, Lu, Nicole, Sragow, John
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2306.10368
The Multiple Drone-Delivery Scheduling Problem (MDSP) is a scheduling problem that optimizes the maximum reward earned by a set of m drones executing a sequence of deliveries on a truck delivery route. The current best-known approximation algorithm for the problem is a (1)/(4)-approximation algorithm developed by Jana and Mandal (2022). In this paper, we propose exact and approximation algorithms for the general MDSP, as well as a unit-cost variant. We first propose a greedy algorithm which we show to be a (1)/(3)-approximation algorithm for the general MDSP problem formulation, provided the number of conflicting intervals is less than the number of drones. We then introduce a unit-cost variant of MDSP and we devise an exact dynamic programming algorithm that runs in polynomial time when the number of drones m can be assumed to be a constant.