On the Complexity of Scheduling in Half-Duplex Diamond Networks

We consider an n-relay Gaussian diamond network where a source communicates to a destination with the help of n half-duplex relays. Achieving rates close to the capacity of this network requires to employ all the n relays under an optimal transmit/receive schedule. Even for the moderate values of n, this can have significant operational complexity as the optimal schedule may possibly have 2(n) different states for the network (since each of the relays can be in either transmitting or receiving mode). In this paper, we investigate whether a significant fraction of the network capacity can be achieved by using transmit/receive schedules that have only few active states and by using only few relays. First, we conjecture that the approximately optimal schedule has at most n+1 states instead of the 2(n) possible states. We prove this conjecture for networks of size n