Efficient algorithms for the data exchange problem under fairness constraints
Nebojsa Milosavljevic, Sameer Pawar, Michael Gastpar, Kannan Ramchandran · 2012
In this paper we study the data exchange problem where a set of users is interested in gaining access to a common file, but where each has only partial knowledge about it as side-information. Given that the collective information of all the users is sufficient to allow recovery of the entire file, the goal is to minimize the sum of convex functions over the number of bits each user has to transmit in order to achieve the goal. A special case of this objective is the uniform cost, which essentially leads to a “fair” communication load distribution among the users. We consider the following side-information settings: (i) side-information in the form of uncoded packets of the file, where the users' side-information consists of subsets of the file packets; and (ii) side-information in the form of linearly correlated packets, where the users have access to linear combinations of the file packets. We provide a polynomial-time deterministic algorithm that finds an optimal communication scheme w.r.t. the transmission cost. To further lower the complexity, we also give a simple randomized algorithm inspired by our deterministic algorithm.