Systems relying on increasingly large and dynamic communication networks must find effective ways to optimally localize service facilities. This can be achieved by efficiently partitioning the system and computing the partitions' centers, solving the classic p-median and p-center problems. These are NP-hard when striving for optimality. Numerous approximate solutions have been proposed during the past 30 years. However, they all fail to address the combined requirements of scalability, optimality and flexibility. Here we present a novel distributed algorithm that computes provably near-optimal p-medians in linear time, exploiting the properties of mobile software agents.