Distributed submodular maximization for optimal resource allocation

About This Grant

In today's rapidly evolving intelligent systems landscape, spanning various smart operations such as traffic and energy grid management to deploying sensors for environmental monitoring, optimizing resource allocation is crucial for efficient decision-making and policy formulation. Despite numerous advances in the field of optimization theory, current methods for optimal resource allocation problems often falter, especially in large, distributed networks where devices must coordinate without the presence of a central authority, resulting in slow solutions and high communication demands. This project addresses these fundamental limitations in combinatorial optimization problems, specifically submodular maximization under matroid constraints—an NP-hard problem that regularly appears in optimal discrete resource allocation. While efficient mathematical approaches have been developed to achieve near-optimal solutions in centralized form for submodular maximization under matroid constraints, these solutions often incur significant computational costs. In distributed settings, in addition to these computational costs, the optimal resource allocation process is further exacerbated by high in-network communication costs and local data disclosure issues. Our objective is to develop practical solutions that reduce in-network communication costs, maintain favorable trade-offs in optimality gaps, and accelerate solutions. The project will deliver practical distributed algorithms with analytically characterized optimality gaps and proven practicality measures. The project will also provide vital educational and training opportunities for students from K-12 to graduate level, preparing the future workforce in optimal decision-making for autonomous systems. This research aims to significantly advance the theory and practice of distributed submodular maximization under partition matroid constraints. We will focus on the continuous relaxation approach, which has improved the optimality gap for centralized solutions from 0.5 to 0.63. Our primary goal is to develop practical distributed algorithms based on this approach that maintain strong optimality guarantees while drastically reducing communication and computational costs. We will achieve this through two key technical avenues: first, by exploring methods like hard-thresholding and localized gradient approximations to limit data exchange among agents; and second, by accelerating convergence rates using novel variance reduction techniques based on control variates and advanced algorithms that reuse gradient information. The project emphasizes rigorous formal analysis to characterize optimality gaps and will validate these algorithms through extensive computer simulations and experimental studies, including applications in multi-agent robotic coverage and smart grid systems. Outcomes will include a catalog of provably correct distributed optimization strategies and open-source software tools. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.