Structure of optimal schedules in diamond networks

We consider Gaussian diamond networks with n half-duplex relays. At any point of time, a relay can either be in a listening (L) or transmitting (T) state. The capacity of such networks can be approximated to within a constant gap (independent of channel SNRs) by solving a linear program that optimizes over the 2(n) relaying states. We recently conjectured, and proved for the cases of n = 2, 3, that there exist optimal schedules with at most n+1 active states, instead of the possible 2(n). In this paper we develop a computational proof strategy that relies on submodularity properties of information flow across cuts in the network and linear programming duality to resolve the conjecture. We implement the strategy for n = 4, 5, 6 and show that indeed there exist optimal schedules with at most n+1 active states in these cases (1).

Published in:
2014 Ieee International Symposium On Information Theory (Isit), 641-645
Presented at:
IEEE International Symposium on Information Theory (ISIT), Honolulu, HI, JUN 29-JUL 04, 2014
New York, Ieee

 Record created 2015-04-13, last modified 2018-09-13

Rate this document:

Rate this document:
(Not yet reviewed)