Approximation Algorithms for Cooperative Multi-Robot Patrolling in Core-Periphery Graph Settings

The adoption of autonomous robots for patrolling introduces efficiency and resilience into automated surveillance systems. A fundamental challenge in this domain lies in optimal planning of patrol routes, a problem typically addressed through graph-based models of the environment. In this work, we consider core-periphery graph settings, where locations are divided into a high-priority core and a lower-priority periphery, a structure that naturally aligns with many real-world scenarios, such as urban surveillance and infrastructure security. We extend the Overlapping Partition Problem (OPP), a recently proposed formalization for core-periphery settings, providing novel theoretical insights by deriving approximation bounds under the assumption that the core is known, a realistic assumption in many surveillance contexts. Our theoretical contributions are complemented by empirical comparisons of our method with two state-of-the-art baselines, demonstrating our method’s superior performance in computing effective patrolling strategies.