Charge me if you can: charging path optimization and scheduling in mobile networks

We study a class of generic optimization problems on charger scheduling and charging path planing. These problems arise from emerging networking applications where mobile chargers are dispatched to deliver energy to mobile agents (e.g., robots, drones, and vehicles), which have specified tasks and mobility patterns. We instantiate our work by focusing on finding the charging path maximizing the number of nodes charged within a fixed time horizon. We prove that this problem is APX-hard. By recursively decomposing the problem into sub-problems of searching sub-paths, we design a quasi-polynomial time algorithm that achieves poly-logarithmic approximation to the optimum charging path. Our approximation algorithm can be further adapted and extended to solve a variety of charging path optimization and scheduling problems with realistic constraints, such as limited time and energy budget.