Journal article

Improving Computational Efficiency of Communication for Omniscience and Successive Omniscience

Ni Ding, Parastoo Sadeghi, Thierry Rakotoarivelo

IEEE TRANSACTIONS ON INFORMATION THEORY | IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC | Published : 2021

Abstract

Communication for omniscience (CO) refers to the problem where the users in a finite set V observe a discrete multiple random source and want to exchange data over broadcast channels to reach omniscience, the state where everyone recovers the entire source. This paper studies how to improve the computational complexity for the problem of minimizing the sumrate for attaining omniscience in V .While the existing algorithms rely on the submodular function minimization (SFM) techniques and complete in O(|V |2 · SFM(|V |) time, we prove the strict strong map property of the nesting SFM problem. We propose a parametric (PAR) algorithm that utilizes the parametric SFM techniques and reduces the com..

View full abstract

University of Melbourne Researchers