The Approximate Optimality of Simple Schedules for Half-Duplex Multi-Relay Networks
arXiv:1410.7174 · doi:10.1109/ITW.2015.7133090
Abstract
In ISIT'12 Brahma, Özgür and Fragouli conjectured that in a half-duplex diamond relay network (a Gaussian noise network without a direct source-destination link and with non-interfering relays) an approximately optimal relay scheduling (achieving the cut-set upper bound to within a constant gap uniformly over all channel gains) exists with at most active states (only out of the possible relay listen-transmit configurations have a strictly positive probability). Such relay scheduling policies are said to be simple. In ITW'13 we conjectured that simple relay policies are optimal for any half-duplex Gaussian multi-relay network, that is, simple schedules are not a consequence of the diamond network's sparse topology. In this paper we formally prove the conjecture beyond Gaussian networks. In particular, for any memoryless half-duplex -relay network with independent noises and for which independent inputs are approximately optimal in the cut-set upper bound, an optimal schedule exists with at most active states. The key step of our proof is to write the minimum of a submodular function by means of its Lovász extension and use the greedy algorithm for submodular polyhedra to highlight structural properties of the optimal solution. This, together with the saddle-point property of min-max problems and the existence of optimal basic feasible solutions in linear programs, proves the claim.
arXiv commentSubmitted to IEEE Information Theory Workshop (ITW) 2015
References in corpus (4)
- On the Capacity of the Half-Duplex Diamond Channel
- Gaussian Half-Duplex Relay Networks: improved constant gap and connections with the assignment problem
- On the Optimality of Simple Schedules for Networks with Multiple Half-Duplex Relays
- On Capacity and Optimal Scheduling for the Half-Duplex Multiple-Relay Channel