  This paper considers the communication for omniscience (CO) problem: A set of
users observe a discrete memoryless multiple source and want to recover the
entire multiple source via noise-free broadcast communications. We study the
problem of how to determine an optimal rate vector that attains omniscience
with the minimum sum-rate, the total number of communications. The results
cover both asymptotic and non-asymptotic models where the transmission rates
are real and integral, respectively. We propose a modified decomposition
algorithm (MDA) and a sum-rate increment algorithm (SIA) for the asymptotic and
non-asymptotic models, respectively, both of which determine the value of the
minimum sum-rate and a corresponding optimal rate vector in polynomial time.
For the coordinate saturation capacity (CoordSatCap) algorithm, a nesting
algorithm in MDA and SIA, we propose to implement it by a fusion method and
show by experimental results that this fusion method contributes to a reduction
in computation complexity. Finally, we show that the separable convex
minimization problem over the optimal rate vector set in the asymptotic model
can be decomposed by the fundamental partition, the optimal partition of the
user set that determines the minimum sum-rate, so that the problem can be
solved more efficiently.
