Improving Computational Efficiency of Communication for Omniscience and Successive Omniscience

Abstract

For a group of users in V where everyone observes a component of a discrete multiple random source, the process that users exchange data so as to reach omniscience, the state where everyone recovers the entire source, is called communication for omniscience (CO). We first consider how to improve the existing complexity O(|V|^{2} \mathrm{S}\mathrm{F} \mathrm{M}(|V|) of minimizing the sum of communication rates in CO, where \mathrm{S}\mathrm{F} \mathrm{M}(|V|) denotes the complexity of minimizing a submodular function. We reveal some structured property in an existing coordinate saturation algorithm: the resulting rate vector and the corresponding partition of V are segmented in \alpha, the es..