A Faster Algorithm for Asymptotic Communication for Omniscience
Ni Ding, Chung Yuen Chan, Qiaoqiao Zhou, Rodney A. Kennedy, Parastoo Sadeghi · 2016
We propose a modified decomposition algorithm (MDA) to solve communication for omniscience (CO) problem in asymptotic model where the transmission rates could be real or fractional. It starts with a lower estimation of the minimum sum-rate and iteratively updates it by the optimizer of a Dilworth truncation problem until the minimum is reached with a corresponding optimal rate vector. We propose a fusion method for solving the Dilworth truncation problem, where the minimization is done over a fused user set. We show that the fusion method contributes to a significant reduction in the computation complexity. We also discuss how to utilize the results returned by the MDA algorithm to solve the non-asymptotic CO problem, where the communication rates are restricted to be integral, and how to choose a proper linear ordering of the user indices so that the optimal rate vector is also the optimizer of a minimum weighted sum-rate problem.