Network Simplification in Half-Duplex: Building on Submodularity

Yahya H. Ezzeldin, Martina Cardone, Christina Fragouli, Daniela Tuninetti

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


This paper explores the network simplification problem in the context of Gaussian half-duplex diamond networks. Specifically, given an N -relay diamond network, this problem seeks to derive fundamental guarantees on the capacity of the best k -relay subnetwork, as a function of the full network capacity. Simplification guarantees are presented in terms of a particular approximate capacity, termed Independent-Gaussian (IG) approximate capacity, that characterizes the network capacity to within an additive gap, which is independent of the channel coefficients and operating SNR. The main focus of this work is when k\!=\!N\!-\!1 relays are selected out of N relays in a diamond network. First, a simple algorithm is proposed which selects all relays except the one with the minimum IG approximate half-duplex capacity. It is shown that the selected (N\!-\!1) -relay subnetwork has an IG approximate half-duplex capacity that is at least 1/2 of the IG approximate half-duplex capacity of the full network and that for the proposed algorithm, this guarantee is tight. Furthermore, this work proves the following tight fundamental guarantee: there always exists a subnetwork of k\!=\!N\!-\!1 relays that have an IG approximate half-duplex capacity that is at least equal to (N-1)/N of the IG approximate half-duplex capacity of the full network. Finally, these results are extended to derive lower bounds on the fraction guarantee when k \in [1:N] relays are selected. The key steps in the proofs lie in the derivation of properties of submodular functions, which provide a combinatorial handle on the network simplification problem for Gaussian half-duplex diamond networks.

Original languageEnglish (US)
Article number8742589
Pages (from-to)6801-6818
Number of pages18
JournalIEEE Transactions on Information Theory
Issue number10
StatePublished - Oct 2019

Bibliographical note

Funding Information:
Manuscript received June 4, 2017; revised June 11, 2019; accepted June 12, 2019. Date of publication June 20, 2019; date of current version September 13, 2019. The research carried out at the University of California, Los Angeles (UCLA) was partially funded by NSF under award number 1514531 and 1314937, and by the UC-NL grant LFR-18-548554. D. Tuninetti was supported in part by NSF under Award 1527059. This paper was presented at the 2016 IEEE International Symposium on Information Theory.

Publisher Copyright:
© 1963-2012 IEEE.


  • Half-duplex relay networks
  • approximate capacity
  • relay scheduling
  • relay selection
  • submodularity


Dive into the research topics of 'Network Simplification in Half-Duplex: Building on Submodularity'. Together they form a unique fingerprint.

Cite this