Computing half-duplex schedules in gaussian relay networks via min-cut approximations

Raul H. Etkin, Farzad Parvaresh, Ilan Shomorony, Amir Salman Avestimehr

Research output: Contribution to journalArticlepeer-review


Computing optimal half-duplex schedules in Gaussian relay networks is a challenging problem due to the lack of an exact capacity characterization and the large number of transmit-receive configurations that must be considered. We approach the problem using a constant-gap capacity approximation based on the cut-set bound with independent encoding at the nodes. We formulate an optimization problem to obtain the cut-set optimal half-duplex schedule and find that it is hard to solve in general. This is because it involves an exponential number of variables, since the number of ways to assign each node to either transmitter or receiver mode is exponential in the number of nodes. We present a general technique that takes advantage of specific structures in the topology of a given network and allows us to reduce the complexity of this problem. In certain classes of network topologies, our approach yields polynomial time algorithms for finding half-duplex schedules that achieve capacity within a constant gap. We use simulations to show running time improvements over alternative methods and compare the performance of various half-duplex scheduling approaches in different SNR regimes.

Original languageEnglish (US)
Article number6905815
Pages (from-to)7204-7220
Number of pages17
JournalIEEE Transactions on Information Theory
Issue number11
StatePublished - Nov 2014
Externally publishedYes


  • Cut-set bound
  • half-duplex networks
  • submodular optimization
  • tree decomposition

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


Dive into the research topics of 'Computing half-duplex schedules in gaussian relay networks via min-cut approximations'. Together they form a unique fingerprint.

Cite this