Tight Bounds for Maximum Weight Matroid Independent Set and Matching in the Zero Communication Model

Recent years have revealed an unprecedented demand for AI-based technology, leading to a common setting where immense data is distributed across multiple locations. This creates a communication bottleneck among the storage facilities, often aiming to jointly solve tasks of small solution size k from input of astro-nomically large size n . Motivated by federated and distributed machine learning applications, we study two fundamental optimization problems, maximum weight matroid independent set (MW-IS) and maximum weight matching (MWM) , in a zero communication computational model. In this model, the data is dispersed between m servers. Without any communication, each server has to send a message to a central coordinator which is required to compute an optimal solution for the original (large) instance. The goal is to minimize the size of the maximum message sent. For this natural restrictive model, we obtain deterministic algorithms that use O ( k ) - data per server for MW-IS and O (cid:0) k 2 (cid:1) -data per server for MWM, where k is the solution size (given to each server). We complement these results with tight lower bounds – ruling out any asymptotic improvement even if randomization is allowed. Our algorithms are simple and run in nearly linear time. Interestingly, we show how our zero communication algorithms yield deterministic parallel algorithms with running times O (cid:16) √ k · log n (cid:17) and O (cid:0) k 4 · log n (cid:1) for MW-IS and MWM, respectively.