On efficient min-cut approximations in half-duplex relay networks

Computing the cut-set bound in half-duplex (HD) relay networks is a challenging optimization problem that involves an exponential number of variables and constraints (exponential in the number of nodes in the network). We present a general technique for efficiently computing the HD schedule that maximizes the cut-set bound (with i.i.d. input distribution) in layered Gaussian relay networks. We use simulations to show running time improvements over alternative methods and compare the performance of various HD scheduling approaches in different SNR regimes.