Modeling and Approximating the Visit of a Set of Sites With a Fleet of UAVs.

This article addresses the problem of coordinating a fleet of self-piloting unmanned aerial vehicles (UAVs) to survey an earthquake-affected area for rescue purposes, modeling it as a novel graph theoretical problem called the Min-Max Rooted Cycle Cover Scheduling Problem (SchedMinCT). The problem involves scheduling UAV tours (cycles) from a base with battery constraints and recharge times to minimize the maximum completion time across all UAVs, and it is proven to be NP-hard. The authors develop an approximation algorithm for SchedMinCT, achieving a performance ratio that becomes constant under certain practical conditions, such as when edge weights are integer-valued or when the maximum distance from the base to any site is bounded by a fixed fraction of the UAV flight time. Furthermore, they establish polynomial-time reductions linking SchedMinCT to known problems like the Minimum Rooted Cycle Cover Problem (RMCCP), showing that the approximability of SchedMinCT inherits the complexity of RMCCP. This work provides a comprehensive theoretical framework for UAV scheduling in disaster scenarios and connects it to existing combinatorial optimization problems, potentially guiding future research on approximation algorithms in this domain.