Conference Proceedings
Improving Computational Efficiency of Communication for Omniscience and Successive Omniscience
Ni Ding, Parastoo Sadeghi, Thierry Rakotoarivelo
2018 56TH ANNUAL ALLERTON CONFERENCE ON COMMUNICATION, CONTROL, AND COMPUTING (ALLERTON) | IEEE | Published : 2018
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..
View full abstract