Graduate School and Research Center in Digital Sciences

The approximate optimality of simple schedules for half-duplex multi-relay networks

Cardone, Martina; Tuninetti, Daniela; Knopp, Raymond

ITW 2015, IEEE Information Theory Workshop, April 26-May 1st, 2015, Jerusalem, Israel

In ISIT2012 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 N 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 N + 1 active states (only N + 1 out of the 2N possible relay listentransmit configurations have a strictly positive probability). Such relay scheduling policies are said to be simple. In ITW2013 we conjectured that simple relay policies are optimal for any halfduplex 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 N-relay network for which the cut-set bound is approximately optimal to within a constant gap under some conditions (satisfied for example by Gaussian networks), an optimal schedule exists with at most N + 1 active states. The key step of our proof is to write the minimum of a submodular function by means of its Lovasz 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 minmax problems and the existence of optimal basic feasible solutions in linear programs, proves the claim.

Document Doi Arxiv Bibtex

Title:The approximate optimality of simple schedules for half-duplex multi-relay networks
Department:Communication systems
Eurecom ref:4431
Copyright: © 2015 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.
Bibtex: @inproceedings{EURECOM+4431, doi = {}, year = {2015}, title = {{T}he approximate optimality of simple schedules for half-duplex multi-relay networks}, author = {{C}ardone, {M}artina and {T}uninetti, {D}aniela and {K}nopp, {R}aymond}, booktitle = {{ITW} 2015, {IEEE} {I}nformation {T}heory {W}orkshop, {A}pril 26-{M}ay 1st, 2015, {J}erusalem, {I}srael}, address = {{J}erusalem, {ISRAEL}}, month = {04}, url = {} }
See also: