M Cardone
email: cardone@eurecom.fr

R Knopp
email: knopp@eurecom.fr

Gaussian Half-Duplex Relay Networks: Improved Constant Gap and Connections with the Assignment Problem Martina Cardone, Daniela Tuninetti, Raymond Knopp and Umer Salim

Abstract-This paper considers a Gaussian relay network where a source transmits a message to a destination with the help of N half-duplex relays. The information theoretic cut-set upper bound to the capacity is shown to be achieved to within 1.96(N + 2) bits by noisy network coding, thereby reducing the previously known gap. This gap is obtained as a special case of a more general constant gap result for Gaussian half-duplex multicast networks. It is then shown that the generalized Degreesof-Freedom of this network is the solution of a linear program, where the coefficients of the linear inequality constraints are proved to be the solution of several linear programs referred as the assignment problem in graph theory, for which efficient numerical algorithms exist. The optimal schedule, that is, the optimal value of the 2 N possible transmit-receive configuration states for the relays, is investigated and known results for diamond networks are extended to general relay networks. It is shown, for the case of N = 2 relays, that only N + 1 = 3 out of the 2 N = 4 possible states have a strictly positive probability and suffice to characterize the capacity to within a constant gap. Extensive experimental results show that, for a general N -relay network with N ≤ 8, the optimal schedule has at most N + 1 states with a strictly positive probability. As an extension of a conjecture presented for diamond networks, it is conjectured that this result holds for any HD relay network and any number of relays. Finally, a network with N = 2 relays is studied in detail to illustrate the channel conditions under which selecting the best relay is not optimal, and to highlight the nature of the rate gain due to multiple relays.

Index Terms-Assignment problem, capacity to within a constant gap, generalized degrees-of-freedom, half-duplex, inner bound, outer bound, relay networks, weighted bipartite matching problem.

I. INTRODUCTION

Cooperation between nodes in a network has been proposed as a potential and promising technique to enhance the performance of wireless systems in terms of coverage, throughput, network generalized Degrees-of-Freedom (gDoF) and robustness / diversity. This last point is of great importance, especially in military and satellite communications, where redundancy and diversity play a significant role, by insuring a more reliable link between two networks (military communication) and two ground stations (satellite communication), with respect to the point-to-point communication.

The simplest form of collaboration can be modeled as a Relay Channel (RC) [START_REF] Cover | Capacity theorems for the relay channel[END_REF]. The RC is a multi-terminal network where a source conveys information to a destination with the help of one relay. The relay has no own data to send and its only purpose is to assist the source in the transmission. Motivated by the undeniable practical importance of the RC, in this paper we analyze a system where the communication between a source and a destination is assisted by multiple relays. In particular, we mainly focus on the enhancement in terms of gDoF due to the use of multiple Half-Duplex (HD) relays. A relay is said to work in HD mode if at any time / frequency instant it can not simultaneously transmit and receive. The HD modeling assumption is at present more practical than the Full-Duplex (FD) one. This is so because practical restrictions arise when a node can simultaneously transmit and receive, such as for example how well the selfinterference can be canceled, making the implementation of FD relays challenging [START_REF] Duarte | Full-duplex wireless communications using off-the-shelf radios: Feasibility and first results[END_REF], [START_REF] Everett | Empowering fullduplex wireless communication by exploiting directional diversity[END_REF].

A. Related work

The RC model was first introduced by van der Meulen [START_REF] Van Der Meulen | Three-terminal communication channel[END_REF] in 1971. Despite the significant research efforts, the capacity of the general memoryless RC is still unknown. In their seminal work [START_REF] Cover | Capacity theorems for the relay channel[END_REF], Cover and El Gamal proposed a general outer bound, now known as the max-flow min-cut outer bound or cut-set for short, and two achievable schemes: decode-and-forward (DF) and compress-and-forward (CF). The cut-set outer bound was shown to be tight for the degraded RC, the reversely degraded RC and the semi-deterministic RC [START_REF] Cover | Capacity theorems for the relay channel[END_REF], but it is not tight in general [START_REF] Aleksic | Capacity of a class of modulo-sum relay channels[END_REF].

Although more study has been conducted for FD relays, there are some important references treating HD ones. In [START_REF] Host-Madsen | On the capacity of wireless relaying[END_REF], the author studied the time-division duplexing RC. Both an outer bound, based on the cut-set argument, and an inner bound, based on partial decode-and-forward (PDF), were developed. In [START_REF] Host-Madsen | On the capacity of wireless relaying[END_REF], the time instants at which the relay switches from listen to transmit and vice versa are assumed fixed, i.e., a priori known by all nodes; we refer to this mode of operation as deterministic switch. In [START_REF] Kramer | Models and theory for relay channels with receive constraints[END_REF], it was shown that higher rates can be achieved by considering a random switch at the relay. In this way the randomness that lies into the switch may be used to transmit (at most one bit per channel use of) further information to the destination. In [START_REF] Kramer | Models and theory for relay channels with receive constraints[END_REF], it was also shown how the memoryless FD framework incorporates the HD one as a special case, and as such there is no need to develop a separate theory for networks with HD nodes.

The pioneering work of [START_REF] Cover | Capacity theorems for the relay channel[END_REF] has been extended to networks with multiple relays. In [START_REF] Kramer | Cooperative strategies and capacity theorems for relay networks[END_REF], the authors proposed several inner and outer bounds for FD relay networks as a generalization of DF, CF and the cut-set bound; it was shown that DF achieves the ergodic capacity of a wireless Gaussian network with uniform phase fading if the phase information is locally available and the relays are close to the source node.

The exact characterization of the capacity region of a general memoryless network is challenging. Recently it has been advocated that progress can be made towards understanding the capacity by showing that achievable strategies are provably close to (easily computable) outer bounds [START_REF] Avestimehr | Wireless network information flow: a deterministic approach[END_REF]. As an example, in [START_REF] Avestimehr | Wireless network information flow: A deterministic approach[END_REF], the authors studied FD Gaussian relay networks with N + 2 nodes (i.e., N relays, a source and a destination) and showed that the capacity can be achieved to within N +2 k=1 5 min{M k , N k } bits with a network generalization of CF named quantize-remap-and-forward (QMF), where M k and N k are the number of transmit and receive antennas, respectively, of node k. Interestingly, the gap result remains valid for static and ergodic fading networks where the nodes operate either in FD mode or in HD mode; however [START_REF] Avestimehr | Wireless network information flow: A deterministic approach[END_REF] did not account for random switch in the outer bound. In [START_REF] Özgür | Approximately achieving Gaussian relay network capacity with lattice-based QMF codes[END_REF], the authors demonstrated that the QMF scheme can be realized with nested lattice codes. Moreover they showed that for single antenna HD networks with N relays, by following the approach of [START_REF] Kramer | Models and theory for relay channels with receive constraints[END_REF], i.e., by also accounting for random switch in the outer bound, the gap is 8(N + 2) bits [START_REF] Özgür | Approximately achieving Gaussian relay network capacity with lattice-based QMF codes[END_REF]. Recently, for single antenna networks with N FD relays, the 5(N + 2) bits gap of [START_REF] Avestimehr | Wireless network information flow: A deterministic approach[END_REF] was reduced to 2 × 0.63(N + 2) bits (where the factor 2 accounts for complex-valued inputs) thanks to a novel ingenious generalization of CF named noisy network coding (NNC) [START_REF] Lim | Noisy network coding[END_REF].

The gap characterization of [START_REF] Lim | Noisy network coding[END_REF] is valid for a general multicast Gaussian network with FD nodes; the gap grows linearly with the number of nodes in the network, which could be a too coarse capacity characterization for networks with a large number of nodes. Smaller gaps can be obtained for more structured networks. For example, a diamond network [START_REF] Schein | The Gaussian parallel relay network[END_REF] consists of a source, a destination and N relays where the source and the destination can not communicate directly and the relays can not communicate among themselves. In other words, a general Gaussian relay network with N relays is characterized by (N + 2)(N + 1) generic channel link gains, while a diamond network has only 2N non-zero channel link gains. In [START_REF] Schein | The Gaussian parallel relay network[END_REF] the case of N = 2 relays was studied and an achievable region based on time sharing between DF and amplify-and-forward (AF) was proposed. In [START_REF] Sanderovich | Communication via decentralized processing[END_REF], the authors considered two specific configurations of a diamond network with a general number of relays (agents), where the relay-destination links are assumed to be lossless; in the first scenario the relays do not have decoding capabilities, while in the second scenario they do. Upper and lower bounds on the capacity were derived and evaluated for the Gaussian noise channel. Moreover the capacity of the deterministic channel when the relays can decode was characterized. The scenarios of [START_REF] Sanderovich | Communication via decentralized processing[END_REF] were further studied in [START_REF] Ong | On the capacity of the binarysymmetric parallel-relay network[END_REF] under the assumption of lossy relay-destination links and where each source-relay link and relay-destination link is a binary-symmetric channel. In [START_REF] Gastpar | On the capacity of large Gaussian relay networks[END_REF], the authors analyzed the Gaussian diamond network with a direct link between the source and the destination and showed that 'uncoded forwarding' at the relays asymptotically achieves the cut-set upper bound when the number of relays goes to infinity. This strategy simply requires that each relay delays the input of one time unit and scales it to satisfy the power constraint.

The capacity of a general Gaussian FD diamond network is known to within 2 log(N + 1) bits [START_REF] Chern | Achieving the capacity of the n-relay Gaussian diamond network within log(n) bits[END_REF], [START_REF] Sengupta | Optimizing quantizemap-and-forward relaying for Gaussian diamond networks[END_REF]. If, in addition, the network is symmetric, that is, all source-relay links are equal and all relay-destination links are equal, the gap is less than 3.6 bits for any N [START_REF] Niesen | Approximate capacity of the Gaussian nrelay diamond network[END_REF].

HD diamond networks have been studied as well. In a HD diamond network with N relays, there are 2 N possible combinations of listening / transmitting states, since each relay, at a given time instant, can either transmit or receive. For the case of N = 2 relays, [START_REF] Bagheri | On the capacity of the half-duplex diamond channel[END_REF] showed that out of 2 N = 4 possible states only N +1 = 3 states suffice to achieve the cut-set bound to within less than 4 bits. We refer to the states with strictly positive probability as active states. The achievable scheme of [START_REF] Bagheri | On the capacity of the half-duplex diamond channel[END_REF] is a clever extension of the two-hop DF strategy of [START_REF] Xue | Cooperation in a half-duplex Gaussian diamond relay channel[END_REF]. In [START_REF] Bagheri | On the capacity of the half-duplex diamond channel[END_REF] a closed-form expression for the aforementioned active states, by assuming no power control and deterministic switch, was derived by solving the dual linear program (LP) associated with the LP derived from the cut-set bound. The work in [START_REF] Brahma | Simple schedules for halfduplex networks[END_REF] studied a general diamond network with N = 2 relays and an 'antisymmetric' diamond network with N = 3 relays and showed that a significant fraction of the capacity can be achieved by: (i) selecting a single relay, or (ii) selecting two relays and allowing them to work in a complementary fashion as in [START_REF] Bagheri | On the capacity of the half-duplex diamond channel[END_REF]. Inspired by [START_REF] Bagheri | On the capacity of the half-duplex diamond channel[END_REF], the authors of [START_REF] Brahma | Simple schedules for halfduplex networks[END_REF] also showed that, for a specific HD diamond network with N = 3 relays, at most N + 1 = 4 states out of the 2 N = 8 possible ones are active. The authors also numerically verified that for a general HD diamond network with N ≤ 7 relays, at most N + 1 states are active and conjectured that the same holds for any number of relays. In [START_REF] Brahma | On the structure of approximately optimal schedules for half-duplex diamond networks[END_REF], this conjecture was proved for the case N = 3 by using the submodularity of the cut-set bound.

Relay networks were also studied in [START_REF] Ong | On capacity and optimal scheduling for the half-duplex multiple-relay channel[END_REF], where an iterative algorithm was proposed to determine the optimal fraction of time each HD relay transmits/receives by using DF with deterministic switch.

B. Contributions

In this work we study a general Gaussian HD relay network, whose exact capacity is unknown, by following the approach proposed in [START_REF] Kramer | Models and theory for relay channels with receive constraints[END_REF]. Our main contributions can be summarized as follows:

1) We prove that NNC with deterministic switch achieves the cut-set bound (properly evaluated to account for random switch) to within 1.96(N + 2) bits. This gap is smaller than the 8(N + 2) bits gap available in the literature [START_REF] Özgür | Approximately achieving Gaussian relay network capacity with lattice-based QMF codes[END_REF]. Our gap result for HD relay networks is obtained as a special case of a more general result for multicast HD Gaussian networks, which extends the 1.26 bits/node gap for the FD case [START_REF] Lim | Noisy network coding[END_REF] to a 1.96 bits/node gap for the HD case. 2) In order to determine the gDoF of the channel, one needs to find a tight high-SNR approximation for the different mutual information terms involved in the cut-set upper bound. As a result of independent interest, we show that such tight approximations can be found as the solution of Maximum Weighted Bipartite Matching (MWBM) problems, or assignment problems [START_REF] Burkard | Assignment Problems[END_REF]. The MWBM problem is a special LP for which efficient polynomialtime algorithms, such as the Hungarian algorithm [START_REF] Kuhn | The Hungarian method for the assignment problem[END_REF], exist. As an example, we show that this technique is useful to derive the gDoF of Gaussian broadcast networks with relays and to solve user scheduling problems. 3) We extend the results of [START_REF] Bagheri | On the capacity of the half-duplex diamond channel[END_REF] for a diamond network with N = 2 relays to the general network. We show that, out of the 2 N = 4 possible states, at most N + 1 = 3 are sufficient to characterize the capacity to within a constant gap. Extensions beyond gDoF are also discussed. Similarly to [START_REF] Brahma | Simple schedules for halfduplex networks[END_REF], we verify through extensive numerical evaluations that, for a general relay network with N ≤ 8 relays, at most N + 1 states are sufficient to characterize the gDoF. Based on this evidence, we conjecture that the conjecture of [START_REF] Brahma | Simple schedules for halfduplex networks[END_REF] holds for any HD relay network. 4) We finally consider a general relay network with N = 2 relays. We highlight under which channel conditions a best-relay selection scheme is strictly suboptimal in terms of gDoF and we gain insights into the nature of the rate gain attainable in networks with multiple relays. For example, we show when the interaction between the relays, which is impossible in diamond networks, can strictly increase the gDoF.

C. Paper organization

The rest of the paper is organized as follows. Section II describes the channel model. Section III shows that the cutset upper bound and the NNC lower bound for a general Gaussian HD multicast network are to within a constant gap from each another, from which the constant gap result for the relay network straightforwardly follows. Section IV proves the equivalence between the problem of finding the coefficients of the linear inequality constraints of the LP derived from the cut-set upper bound and the MWBM problem; it also shows that, for a 2-relay network, the number of active states in the cut-set upper bound is at most 3 for any SNR and any input distributions; it finally presents a conjecture regarding the maximum number of active states sufficient to characterize the cut-set upper bound for a general relay network and for any number of relays. Section V provides an example of a HD relay network with N = 2 relays; it determines under which channel conditions the gDoF achieved with the best-relay selection strategy is strictly smaller than the gDoF attained by exploiting both relays; it provides insights into the synergies of multiple relays. Section VI concludes the paper. The proofs can be found in Appendix.

D. Notation

We use the notation convention of [START_REF] Gamal | Network Information Theory[END_REF]. [n 1 : n 2 ] is the set of integers from n 1 to n 2 ≥ n 1 . [x] + := max{0, x} for x ∈ R. Y j is a vector of length j with components (Y 1 , . . . , Y j ). For an index set A we let Y A = {Y j : j ∈ A}. 0 j denotes either the all-zero column vector of length j or the all-zero square matrix of dimension j, which one is usually clear from the context. 1 j is a column vector of length j of all ones. I j is the identity matrix of dimension j. f 1 (x) . = f 2 (x) means that lim x→∞ f 1 (x)/f 2 (x) = 1. |A| indicates either the determinant of the matrix A or the cardinality of the set A, which one is usually clear from the context, while a is the Euclidean length of the vector a. To indicate a sub matrix of the matrix A where only the rows indexed by the set R and the columns indexed by the set C are retained, we use the Matlab-inspired notation A R,C . Moreover, for a square matrix A, diag[A] is a vector containing the diagonal elements of A, while for a vector a we let diag[a] be a diagonal matrix with the entries of a on the main diagonal, i.e., diag [a]

ij = a i δ[i -j],
where δ[n] = 0 n = 0 1 n = 0 is the Kronecker delta function.

X ∼ N µ, σ 2 indicates that X is a proper-complex Gaussian random variable with mean µ and variance σ 2 .

II. SYSTEM MODEL

A. General memoryless relay network

A memoryless relay network has one source (node 0), one destination (node N + 1), and N relays indexed from

1 to N . It consists of N + 1 input alphabets (X 1 , • • • , X N , X N +1 )
(here X i is the input alphabet of node i except for the source/node 0 where, for notation convenience, we use X N +1 rather than X 0 ),

N + 1 output alphabets (Y 1 , • • • , Y N , Y N +1 )
(here Y i is the output alphabet of node i), and a transition probability

P Y [1:N +1] |X [1:N +1]
. The source has a message W uniformly distributed on [1 : 2 nR ] for the destination, where n denotes the codeword length and R the transmission rate in bits per channel use (logarithms are in base 2). At time i, i ∈ [1 : n], the source maps its message W into a channel input symbol X N +1,i (W ), and the k-th relay, k ∈ [1 : N ], maps its past channel observations into a channel input symbol

X k,i Y i-1 k
. The channel is assumed to be memoryless, that is, the following Markov chain holds for all i ∈ [1 : n]

(W, Y i-1 [1:N +1] , X i-1 [1:N +1] ) → X [1:N +1],i → Y [1:N +1],
i . At time n, the destination outputs an estimate of the message based on all its channel observations as W Y n N +1 . A rate R is said to be ǫ-achievable if there exists a sequence of codes indexed by the block length n such that P[ W = W ] ≤ ǫ for some ǫ ∈ [0, 1]. The capacity is the largest non-negative rate that is ǫ-achievable for any ǫ > 0.

In this general memoryless framework, each relay can listen and transmit at the same time, i.e., it is a FD node. HD channels are a special case of the memoryless FD framework in the following sense [START_REF] Kramer | Models and theory for relay channels with receive constraints[END_REF]. With a slight abuse of notation compared to the previous paragraph, we let the channel input of the k-th relay, k ∈ [1 : N ], be the pair (X k , S k ), where X k ∈ X k as before and S k ∈ [0 : 1] is the state random variable that indicates whether the k-th relay is in receive-mode (S k = 0) or in transmit-mode (S k = 1). In the HD case the transition probability is specified as

P Y [1:N +1] |X [1:N +1] ,S [1:N ] . In particular, when the k-th relay, k ∈ [1 : N ],
is listening (S k = 0) the outputs are independent of X k , while when the k-th relay is transmitting (S k = 1) its output Y k is independent of all other random variables. By adopting this convention, there is no need to develop a separate theory for HD channels, but the HD constraints can be incorporated into the FD framework. For example, with N = 1 relay the channel transition probability is specified by

P Y1,Y2|X1,X2,S1=0 = P Y1,Y2|X2,S1=0 P Y1,Y2|X1,X2,S1=1 = P Y2|X1,X2,S1=1 P Y1|S1=1
where Y 1 is the relay output, Y 2 the destination output, X 1 the relay input, X 2 the source input, and S 1 the relay state. The generalization to an arbitrary number of relays N follows straightforwardly.

B. The Gaussian HD relay network

The single-antenna complex-valued power-constrained Gaussian HD relay network is described by the input/output relationship

Y = H eq X + Z ∈ C N +1×1 , (1a)
H eq := I N -diag[S] 0 N 0 T N 1 H diag[S] 0 N 0 T N 1 (1b)
where

• Y := [Y 1 , . . . , Y N , Y N +1 ] T ∈ C N +1×1 is the vector of the received signals. • X := [X 1 , . . . , X N , X N +1 ] T ∈ C N +1×1
is the vector of the transmitted signals (recall that, although the source is referred to as node 0, its input is indicated as X N +1 rather than X 0 ). Without loss of generality, we assume that the inputs are subject to the average power constraint

E |X k | 2 ≤ 1, k ∈ [1 : N + 1]. • S := [S 1 , . . . , S N ] T ∈ [0 : 1] N is the vector of the binary relay states, which takes into account if the k-th relay is receiving (S k = 0) or transmitting (S k = 1) for k ∈ [1 : N ]. • H ∈ C (N +1)×(N +1) is the constant channel matrix
known by all terminals defined as

H := H r→r H s→r H r→d H s→d . (2)
The entry in position (i, j) of the channel matrix in (2) represents the channel from node j to node i, (i, j) ∈ [1 :

N + 1] 2 .
H is assumed to be static and therefore known to all nodes. In particular:

-H r→r ∈ C N ×N defines the network connections among relays, i.e., [H r→r ] ij , (i, j) ∈ [1 : N ] 2 , is the channel gain from the j-th relay to the i-th relay.

Notice that the entries on the main diagonal of H r→r do not matter for the channel capacity since the relays operate in HD mode; -H s→r ∈ C N ×1 is the column vector which contains the channel gains from the source to the relays, i.e.,

[H s→r ] i,1 , i ∈ [1 : N ],
is the channel gain from the source to the i-th relay; -H r→d ∈ C 1×N is the row vector which contains the channel gains from the relays to the destination, i.e.,

[H r→d ] 1,i , i ∈ [1 : N ],
is the channel gain from the i-th relay to the destination; -H s→d ∈ C 1×1 is the channel gain between the source and the destination (recall that by our notation the source input is indicated as X N +1 rather than X 0 ).

• Z := [Z 1 , . . . , Z N , Z N +1 ] T ∈ C N +1×1
is the jointly Gaussian noise vector. Without loss of generality, the noises are assumed to have zero mean and unit variance. Furthermore we assume, not without loss of generality [START_REF] Zhang | Study of Gaussian relay channels with correlated noises[END_REF], that the noises are independent, i.e., the covariance matrix of Z is the identity matrix. The capacity of the Gaussian HD relay network in ( 1) is not known in general. In order to evaluate the ultimate performance of this system we make use of two metrics: the gDoF and the capacity to within a constant gap.

The capacity to within a constant gap is defined as:

Definition 1.
The capacity C of the Gaussian HD relay network in (1) is said to be known to within GAP bits if one can show an achievable rate R (in) and an outer bound R (out) such that

R (in) ≤ C ≤ R (out) ≤ R (in) + GAP, ( 3
)
where GAP is a constant that does not depend on the channel gains matrix H in [START_REF] Cardone | Gaussian halfduplex relay networks: Improved gap and a connection with the assignment problem[END_REF].

Knowing the capacity to within a constant gap implies the exact knowledge of the gDoF defined as: Definition 2. The gDoF of the Gaussian HD relay network in (1) is defined as

d := lim SNR→+∞ C log(1 + SNR) , ( 4
)
where C is the capacity and SNR ∈ R + parameterizes the channel gains as

|h ij | 2 = SNR βij , for some fixed non-negative β ij , (i, j) ∈ [1 : N + 1] 2 .
The gDoF in ( 4) is an exact characterization of the capacity at high-SNR, while the capacity to within a constant gap in (3) quantifies how far inner and outer bounds are in the worst SNR scenario.

III. CAPACITY TO WITHIN A CONSTANT GAP

This section is devoted to the capacity characterization of the Gaussian HD relay network in (1) to within a constant 5) (solid curve) and gap in (6) (dashed curve) for the HD Gaussian relay network. The gap in ( 5) is smaller than that in (6) for any N ≥ 2.

gap. We first adapt the cut-set upper bound [START_REF] Kramer | Cooperative strategies and capacity theorems for relay networks[END_REF] and the NNC lower bound [START_REF] Lim | Noisy network coding[END_REF] to the HD case by following the approach proposed in [START_REF] Kramer | Models and theory for relay channels with receive constraints[END_REF]. We then show that these bounds are at most a constant number of bits apart. Our result is:

Theorem 1. The cut-set upper bound for the Gaussian HD relay network with N relays is achievable by NNC with deterministic switch to within

GAP ≤ 1.96(N + 2) bits. ( 5
)
Proof: We first prove that for a multicast single-antenna complex-valued Gaussian network with HD power-constrained nodes the cut-set upper bound can be achieved to within 1.96 bits/node (while for the FD case the gap is 1.26 bits/node [START_REF] Lim | Noisy network coding[END_REF]Theorem 4]). The unicast Gaussian network with HD relays is a special multicast network with K = N + 2 nodes (i.e., one source, N relays, and one destination), which proves the claimed result in [START_REF] Van Der Meulen | Three-terminal communication channel[END_REF]. The derivation of the gap result for the multicast network can be found in Appendix A.

Remark 1. The gap in Theorem 1 improves on the previously known gap result of 8(N + 2) bits [START_REF] Özgür | Approximately achieving Gaussian relay network capacity with lattice-based QMF codes[END_REF].

Remark 2 (Single relay case). The gap result in [START_REF] Van Der Meulen | Three-terminal communication channel[END_REF] for N = 1 gives GAP ≤ 5.88 bits, which is greater than the 1.61 bits gap we found in [START_REF] Cardone | The capacity to within a constant gap of the Gaussian half-duplex relay channel[END_REF]. This is due to the fact that the bounding steps in the special case of N = 1 are tighter than those we used here for a general multicast network with K nodes.

Notice also that for a single relay, PDF is optimal to within 1 bit [START_REF] Cardone | The capacity to within a constant gap of the Gaussian half-duplex relay channel[END_REF]. PDF has been extended to a general HD multi-relay network in [START_REF] Rost | Achievable rates in Gaussian half-duplex multiple relay networks[END_REF]. However, to analytically evaluate this region and show that it achieves the cut-set upper bound to within a constant gap seems to be a challenging task, which is the main motivation for considering NNC here.

Remark 3. In a preliminary version of this work [START_REF] Cardone | Gaussian halfduplex relay networks: Improved gap and a connection with the assignment problem[END_REF], by using a bounding technique as in [32, pages 20-5, 20-7] we obtained

GAP ∼ = N + 2 2 log (4(N + 2)) bits. (6)
As shown in Fig. 1 the gap in ( 5) is smaller that the one in [START_REF] Aleksic | Capacity of a class of modulo-sum relay channels[END_REF] for N ≥ 2 thanks to the tighter bound derived from [13, Lemma 1].

Remark 4 (Diamond networks). A smaller gap than the one in ( 5) may be obtained for specific network topologies. For example, in [START_REF] Chern | Achieving the capacity of the n-relay Gaussian diamond network within log(n) bits[END_REF] and [START_REF] Sengupta | Optimizing quantizemap-and-forward relaying for Gaussian diamond networks[END_REF] it was found that for a Gaussian FD diamond network with N relays the gap is of the order log(N ), rather than linear in N [START_REF] Lim | Noisy network coding[END_REF]. Moreover, for a symmetric FD diamond network with N relays the gap does not depend on the number of relays and it is upper bounded by 3.6 bits [START_REF] Niesen | Approximate capacity of the Gaussian nrelay diamond network[END_REF]. The key difference between a general relay network and a diamond network is that for each subset A we have that rank

[H A ] ≤ 2; hence in (31b) we can use rank[H A ] ≤ min{|A|, |A c |, 2}.
With this and by numerically evaluating the resulting gap we obtain the result plotted in Fig. 2. From Fig. 2, we observe that the gap for the HD diamond network is in general smaller than the one computed for the general HD relay network; this is in line with what happens in FD. However, in FD for the diamond network the gap is logarithmic in N [START_REF] Chern | Achieving the capacity of the n-relay Gaussian diamond network within log(n) bits[END_REF], [START_REF] Sengupta | Optimizing quantizemap-and-forward relaying for Gaussian diamond networks[END_REF], while the gap in Fig. 2 (solid curve) still grows linearly with N . This is due to the fact that the HD cut-set outer bound, as opposed to the FD one, contains the entropy of the state vector, which is upper bounded by the uniform distribution over the all possible states; this term contributes linearly in the number of nodes to the overall gap. Moreover, from Fig. 2 we observe that our gap (solid curve) is larger than the gap of order N +3 log(N ) from [START_REF] Brahma | On the structure of approximately optimal schedules for half-duplex diamond networks[END_REF] (dashed curve). We believe that the reason is because our gap has been computed as a special case of a general HD multicast network while the one in [START_REF] Brahma | On the structure of approximately optimal schedules for half-duplex diamond networks[END_REF] has been specifically derived for HD diamond relay networks.

As we shall see in the next section, for a general HD network with N relays, only N + 1 states, out of the possible 2 N states, appear to be needed to characterize the cut-set upper bound. It is subject of current investigation on how to use this observation to develop bounds leading to a smaller gap.

IV. ANALYSIS OF THE OPTIMAL SCHEDULE

In general, for a N -relay network, 2 N states are possible. A capacity achieving scheme must optimize the probability with which each of these states occurs. In [START_REF] Bagheri | On the capacity of the half-duplex diamond channel[END_REF], it was proved that for a diamond network with N = 2 relays, out of the 2 N = 4 possible states, at most N + 1 = 3 are active / have a non-zero probability. In [START_REF] Brahma | On the structure of approximately optimal schedules for half-duplex diamond networks[END_REF], the authors extended the result of [START_REF] Bagheri | On the capacity of the half-duplex diamond channel[END_REF] to a diamond network with N = 3 relays. Based on numerical evidences, [START_REF] Brahma | Simple schedules for halfduplex networks[END_REF] conjectured that for a N -relay diamond network out of the 2 N possible states at most N + 1 states are active. Here we extend these results to a general Gaussian HD relay network as follows. The claim "out of 2 N possible states only N + 1 states are active as far as gDoF is concerned" is proved analytically for N = 2, shown to hold by numerical evaluations for N ≤ 8 and conjectured to hold for any N . If the conjecture were true, it would show that HD relay networks have intrinsic properties regardless of to the HD diamond network (solid curve) and gap in [START_REF] Brahma | On the structure of approximately optimal schedules for half-duplex diamond networks[END_REF] (dashed curve) for the HD diamond network.

their topology, i.e., known results for diamond networks are not a consequence of the simplified network topology.

In order to determine the gDoF we must find a tight high-SNR approximation for the different MIMO-type mutual information terms involved in the cut-set upper bound (see eq.(31a) in Appendix A). As a result of independent interest beyond the application to the Gaussian HD relay network studied in this paper, we first show that such an approximation can be found as the solution of a Maximum Weighted Bipartite Matching (MWBM) problem.

A. The maximum weighted bipartite matching (MWBM) problem and its relation to the gDoF

In graph theory, a weighted bipartite graph, or bigraph, is a graph whose vertices can be separated into two sets such that each edge in the graph has exactly one endpoint in each set. Moreover, a non-negative weight is associated with each edge in the bigraph [START_REF] Lovasz | Matching Theory[END_REF]. For a general network we define the weight matrix B as follows: there is one set of n 1 nodes, where n 1 is the number of rows in B, and another set of n 2 nodes, where n 2 is the number of columns in B; the element [B] ij is the weight of the edge between nodes i and j. A matching, or independent edge set, is a set of edges without common vertices [START_REF] Lovasz | Matching Theory[END_REF]. The MWBM problem, or assignment problem, is defined as a matching where the sum of the edge weights in the matching has the maximal value [START_REF] Burkard | Assignment Problems[END_REF]. The Hungarian algorithm is a polynomial time algorithm that efficiently solves the assignment problem [START_REF] Kuhn | The Hungarian method for the assignment problem[END_REF]. Equipped with these definitions, we now show the following high-SNR approximation of the MIMO capacity: Theorem 2. Let H ∈ R k×n be a full-rank matrix, where without loss of generality k ≤ n. Let S n,k be the set of all k-combinations of the integers in [1 : n] and P n,k be the set of all k-permutations of the integers in [1 : n]1 . Then,

|I k + HH H | = ς∈S n,k π∈P n,k k i=1 [H ς ] i,π(i) 2 + T . = SNR MWBM(B) , (7)
MWBM(B) := max

ς∈S n,k max π∈P n,k k i=1 [B ς ] i,π(i) , ( 8
)
where B is the SNR-exponent matrix defined as Proof: The proof can be found in Appendix B. The expression in ( 8) is a possible way of writing the MWBM problem.

[B] ij = β ij ≥ 0 : |h ij | 2 = SNR βij ,
Theorem 2 establishes an interesting connection between the gDoF of a MIMO channel (with independent inputs) and graph theory. Notice that the high-SNR expression found in Theorem 2 holds for correlated inputs as well, as long as the average power constraint is a finite constant. More importantly, Theorem 2 allows to move from DoF, where all exponents β ij have the same value, to gDoF, where different channel gains have different exponential behavior. DoF is essentially a characterization of the rank of the channel matrix; gDoF captures the potential advantage due to 'asymmetric' channel gains. gDoF, to the best of our knowledge, has been investigated so far only for Single-Input-Single-Output (SISO) networks with very few number of nodes; we believe that the reason is that in these cases one has only to consider equivalent Multiple-Input-Single-Output (MISO) and Single-Input-Multiple-Output (SIMO) channels, or to explicitly deal with determinants of matrices with small dimensions. Our result extends the gDoF analysis to any MIMO channel as we explain through some examples.

1) MISO and SIMO channels, i.e., the case k = 1 ≤ n: In a MISO or SIMO channel, with channel vector h := 2) 2 × 2 MIMO channels, i.e., the case k = n = 2: As another example from the 2-user interference channel literature, consider the cut-set sum-rate upper bound Notice that the MWBM is a tight approximation of the 2×2 MIMO capacity only if the channel matrix is full rank, see [34, eq.(5) 1st line], but it is loose when the channel matrix is rank deficient, see [34, eq.(5) 2nd line, and compare with eq.( 11)]. The reason is that the MWBM can not capture the impact of phases in MIMO situations. To exclude the case of a rank deficient channel matrix from our general setting for any value of k and n, we may proceed as in [35, page 2925]. Namely, we pose a reasonable distribution, such as for example the i.i.d. uniform distribution, on the phases θ ji , i ∈ [3 : 4], j ∈ [1 : 2], so that almost surely the channel matrix is full rank.

[h 1 , . . . , h n ] such that |h k | 2 = SNR β k , k ∈ [1 : n], one trivially has log(1 + h 2 ) = log 1 + n i=1 SNR βi SNR≫1 . = log SNR max i∈[1:n] {βi} .

The corresponding MWBM problem has one set of vertices

H := h 13 h
3) Relay-aided broadcast channels: In general, Theorem 2 allows to find the gDoF region for any Gaussian network whose capacity can be approximated to within a constant gap by linear combinations of log | . . . | terms. For example, [START_REF] Kannan | Approximately optimal wireless broadcasting[END_REF] studied a channel where one source communicates with K destinations with the help of L FD relays. The cut-set outer bound on the capacity region of such a network is shown to be achievable to within O (N log(N )) bits, where N = K +L+1 is the total number of nodes. This constant gap result implies the exact knowledge of the gDoF region. As an example of application of Theorem 2, we next show how to derive the sum gDoF of the relay-aided broadcast channel.

Consider a relay-aided broadcast channel with one source, K destinations, and L = 1 relay (the result can be straightforwardly extended to the case of multiple relays, of cooperation among destinations and with generalized feedback at the source). The source has input X 0 , the relay has input X 1 , the k-th destination has output

Y k = SNR β k,0 X 0 + SNR β k,1 e jθ k,1 X 1 +Z k , k ∈ [1 : K],
and the relay has output

Y R = SNR βR X 0 + Z R ,
where, since the channel is known to all nodes, each receiving node compensates for the phase of the link from the source. We assume that the phases {θ k,1 , k ∈ [1 : K]} are such that all involved channel (sub)matrices are full rank almost surely. Without loss of generality, we let β 1,0 = max k∈[1:K] {β k,0 }, i.e., destination 1 has the strongest link from the source. We define the gDoF of destination k as

d k = lim SNR→∞ R k log(1+SNR) , k ∈ [1 : K].
The capacity region of this relay-aided broadcast channel is to within a constant gap from the cut-set upper bound [START_REF] Kannan | Approximately optimal wireless broadcasting[END_REF]. The cut-set outer bound yields for all A ⊆

[1 : K], A = ∅, k∈A R k ≤ I(X 0 , X 1 ; Y A ), ( 9a
) k∈A R k ≤ I(X 0 ; Y A , Y R |X 1 ). (9b)
The sum gDoF (and similarly for any other bounds) is the minimum of two terms: the first term from (9a

) with A = [1 : K] is K k=1 d k ≤ MWBM       β 1,0 β 1,1 . . . . . . β K,0 β K,1       = max j∈[2:K] {β 1,0 + β j,1 , β j,0 + β 1,1 } , (10a)
and the second term from (9b

) with A = [1 : K] is K k=1 d k ≤ MWBM β 1,0 . . . β K,0 β R = max {β 1,0 , β R } , (10b)
from the assumption

β 1,0 ≥ β k,0 , k ∈ [2 : K].
The closed-form expression for the gDoF in [START_REF] Avestimehr | Wireless network information flow: a deterministic approach[END_REF] sheds light into approximately optimal achievable schemes: if β R ≤ β 1,0 = max k∈[1:K] {β k,0 } the sum-gDoF is as for the broadcast channel without a relay (i.e., in practical wireless broadcast networks it might not be worth using a relay if the sourcerelay link is weaker than the strongest source-destination link), while if β 1,0 < β R it is sum-gDoF optimal to serve at most one extra destination in addition to destination 1 (see eq.(10a)).

With L relays, it is sum-gDoF optimal to serve at most L + 1 destinations; which subset of destinations to serve can be found by examining the 2 L MWBM-based bounds, in the spirit of [START_REF] Avestimehr | Wireless network information flow: a deterministic approach[END_REF]. This example shows that Theorem 2 is an efficient tool to characterize the gDoF region and it is not only restricted to networks with a small number of nodes. Moreover, this example shows that the result in Theorem 2 also represents an useful tool to solve user scheduling problems.

[A] 7,5 = MWBM             0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1        
        1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1         {3,4},{1,2,4}     = MWBM β 31 0 β 34 β 41 0 β 44 = max {β 31 + β 44 , β 34 + β 41 } (11)
B. The gDoF for a general N -relay network With Theorem 2 we can express the gDoF d in (4) of the Gaussian HD relay network in (1) as a LP. In particular, let

f T := [0 T 2 N , 1] (12a)
x

T := [λ vect , d] (12b)
λ vect := [λ s ] ∈ R 1×2 N + where λ s := P[S [1:N ] = s] ∈ [0, 1], ∀s ∈ [0 : 1] N : s∈[0:1] N λ s = 1, (12c) then d = max{f T x} (12d) s.t. -A 1 2 N 1 T 2 N 0 x ≤ f , x ≥ 0, (12e)
where the non-negative matrix A ∈ R 2 N ×2 N has entries (recall that, although the source is referred to as node 0, its input is indicated as X N +1 rather than X 0 )

[A] ij := lim SNR→+∞ I(X Ai∪{N +1} ; Y A c i ∪{N +1} |X A c i , S [1:N ] = s j ) log(1 + SNR) , (12f)
where A i and s j are defined right after Theorem 3. In other words, each row of the matrix A refers to a possible cut in the network, while each column of A refers to a possible listening/transmitting configuration. By a simple application of Theorem 2 we have that each entry of the matrix A can be evaluated by solving the corresponding MWBM problem. More formally Theorem 3. For the LP in eq.( 12)

[A] ij = MWBM B {N +1}∪(A c i ∩A c j ), {N +1}∪(Ai∩Aj } .
The notation in eq.(12f) and in Theorem 3 is as follows. B indicates the SNR-exponent matrix defined as

[B] ij = β ij ≥ 0 : |h ij | 2 = SNR βij ,
and the indices (i, j) have the following meaning. Index i refers to a "cut" in the network and index j to a "state of the relays". Both indices range in [1 : 2 N ] and must be seen as the decimal representation of a binary number with N bits. A i , i ∈ [1 : 2 N ], is the set of those relays who have a one in the corresponding binary representation of i -1 and s j , j ∈ [1 : 2 N ], sets the state of a relay to the corresponding bit in the binary representation of j -1. Finally, we evaluate the MWBM of the bigraph with weight matrix

I N -diag[s j ] 0 N 0 T N 1 B diag[s j ] 0 N 0 T N 1 {N+1}∪A c i ,{N+1}∪Ai = B {N +1}∪(A c i ∩A c j ), {N +1}∪(Ai∩Aj } ,
where the equality follows from the following observation. Among the relays 'on the side of the destination' (indexed by A c i ) only those in receive mode matter (indexed by A c j ), therefore we can reduce the set of 'receiving nodes' from

A c i to A c i ∩ A c j .
Similarly, among the relays 'on the side of the source' (indexed by A i ) only those in transmit mode matter (indexed by A j ), therefore we can reduce the set of 'transmitting nodes' from A i to A i ∩ A j . Notice that B {N +1}∪(A c i ∩A c j ), {N +1}∪(Ai∩Aj } does not change if the roles of i and j are swapped, which implies that [A] ij = [A] ji , i.e., the matrix A is symmetric.

To better understand the notation, consider the following example.

Example 1 (N = 3, i = 7, and j = 5). From i -

1 = 6 = 1•2 2 +1•2 1 +0•2 0 we have A 7 = {1, 2} = {3} c ,
meaning that relay 1 and relay 2 lie in the cut of the source and relay 3 lies in the cut of the destination. From j -1 = 4 = 1•2 2 +0•2 1 +0•2 0 we have s 5 = [1, 0, 0], meaning that relay 1 is transmitting, and relays 2 and 3 are receiving (also A 5 = {1} = {2, 3} c ). With this we have

{N + 1} ∪ A c i = {4} ∪ {3} = {3, 4}, {N + 1} ∪ A i = {4} ∪ {1, 2} = {1, 2, 4}, {N + 1} ∪ (A c i ∩ A c j ) = {4} ∪ ({3} ∩ {2, 3}) = {3, 4}, {N + 1} ∪ (A i ∩ A j } = {4} ∪ ({1, 2} ∩ {1}) = {1, 4},
and therefore [START_REF] Avestimehr | Wireless network information flow: A deterministic approach[END_REF], at the top of the page, holds. Also One interesting question is how many λ s , i.e., λ s is the probability the network is in state s ∈ [0 : 1] N , are strictly positive [START_REF] Bagheri | On the capacity of the half-duplex diamond channel[END_REF], [START_REF] Brahma | Simple schedules for halfduplex networks[END_REF]. In [START_REF] Bagheri | On the capacity of the half-duplex diamond channel[END_REF], the authors analyzed the diamond network with N = 2 relays and showed that out of the 2 N = 4 possible states only N + 1 = 3 states are active. The proof considers the dual of the LP in [START_REF] Özgür | Approximately achieving Gaussian relay network capacity with lattice-based QMF codes[END_REF]. Here we extend the result of [START_REF] Bagheri | On the capacity of the half-duplex diamond channel[END_REF] to the fully-connected HD relay network with N = 2 relays; our proof identifies the channel conditions under which setting the probability of one of the states to zero is without loss of optimality. We have: Theorem 4. For a general HD relay network with N = 2 relays, there exists a schedule optimal to within a constant Proof: The proof can be found in Appendix C. Notice that the statement holds for any memoryless HD relay network with N = 2 relays. In particular, it holds for the Gaussian noise case, at any SNR and for any input distribution; it therefore holds for the gDoF as well.

We conjecture that for a general HD relay network with any number of relays Theorem 4 continues to hold, similarly to the conjecture presented in [START_REF] Brahma | Simple schedules for halfduplex networks[END_REF] for the diamond network.

Conjecture. For a general HD relay network with N relays, there always exists a schedule optimal to within a constant gap, and hence a schedule that maximizes d in (12d), with at most N + 1 active states.

The conjecture holds for the case of N = 2 relays as proved in Theorem 4. For N > 2, in our numerical simulations, we consider the gDoF. In particular, we proceeded through the following numerical evaluations: for each value of N ≤ 8, we randomly generated the SNR exponents of the channel gains, we computed the entries of A in [START_REF] Özgür | Approximately achieving Gaussian relay network capacity with lattice-based QMF codes[END_REF] with the Hungarian algorithm, we solved the LP in [START_REF] Özgür | Approximately achieving Gaussian relay network capacity with lattice-based QMF codes[END_REF] with the simplex method and we counted the number of constraints that equal the optimal gDoF (which is a known upper bound on the number of non zero entries of an optimal solution). The minimum and the maximum number of active states were found to be 1 and N + 1, respectively, as shown in Fig. 3, which also shows the average number of active states computed by giving an equal weight to all the tried channels. If the reduction of the number of active states from exponential to linear as conjectured holds, it offers a simpler and more amenable way to design the network [START_REF] Brahma | Simple schedules for halfduplex networks[END_REF].

V. FULLY-CONNECTED RELAY NETWORK WITH N = 2

RELAYS

To gain insights into how relays are best utilized, we consider a network with N = 2 relays. The analysis presented here differs from the one in [START_REF] Brahma | Simple schedules for halfduplex networks[END_REF] in the following: (i) we study the fully-connected network, while in [START_REF] Brahma | Simple schedules for halfduplex networks[END_REF] only the diamond network is treated; (ii) we explicitly find under which channel conditions the gDoF performance is enhanced by exploiting both relays instead of using only the best one, and (iii) we provide insights into the nature of the rate gain in networks with multiple HD relays.

We consider the parameterization in [START_REF] Lim | Noisy network coding[END_REF] where, in order to increase the readability of the document, the SNR-exponents are indicated as

log(|h ij | 2 ) log(SNR) (i,j)∈[1:3] 2 =   ⋆ β 1 α s1 β 2 ⋆ α s2 α 1d α 2d 1   , (13)
where ⋆ denotes an entry that does not matter for channel capacity, α si is the SNR-exponent on the link from the source to relay i, i ∈ [1 : 2], α id is the SNR-exponent on the link from relay i, i ∈ [1 : 2], to the destination, β i is the SNR-exponent on the link from relay j to relay i, (i, j) ∈ [1 : 2] 2 with j = i, and the direct link from the source to the destination (entry in position [START_REF] Duarte | Full-duplex wireless communications using off-the-shelf radios: Feasibility and first results[END_REF][START_REF] Duarte | Full-duplex wireless communications using off-the-shelf radios: Feasibility and first results[END_REF] in ( 13)) has SNR-exponent normalized to 1 without loss of generality. Notice that in order to consider a network without a direct link it suffices to consider all the other SNR-exponents to be larger than 1, or simply replace '1' with '0' in the discussion in the rest of the section. We next derive the gDoF in both the FD and HD cases.

A. The full-duplex case

For the FD case, the cut-set bound is achievable to within 2 × 0.63 × 4 = 5.04 bits with NNC [START_REF] Lim | Noisy network coding[END_REF]. As a consequence, it can be verified that the gDoF for the FD case is

d (FD) N =2 = min max {1, α s1 , α s2 } , max {α s2 +α 1d , β 2 +1} , max {α s1 + α 2d , β 1 + 1} , max {1, α 1d , α 2d } . (14)
Notice that d (FD) N =2 ≥ 1, i.e., the gDoF in ( 14) is no smaller than the gDoF that could be achieved without using the relays, that is, by communicating directly through the direct link to achieve gDoF = 1. Notice also that the gDoF in [START_REF] Schein | The Gaussian parallel relay network[END_REF] does not change if we exchange α s1 with α 2d , and α s2 with α 1d , i.e., if we swap the role of the source and destination. We aim to identify the channel conditions under which using both relays strictly improves the gDoF compared to the best-relay selection policy (which includes direct transmission from the source to the destination as a special case) that achieves

d (FD) N =2,best relay = max 1, min{α s1 , α 1d }, min{α s2 , α 2d } ∈ [1, d (FD) N =2 ]. (15)
We distinguish the following cases: Case 1):

if either α s1 ≥ α s2 α 1d ≥ α 2d or α s1 < α s2 α 1d < α 2d
then, since one of the relays is 'uniformly better' than the other, we immediately see that d

(FD) N =2 = d (FD)
N =2,best relay , so in this regime selecting the best relay for transmission is gDoF optimal. either max{1, α s2 , α 1d } < min{α s1 , α 2d } ≤ max {α s2 + α 1d , β 2 + 1}

or max {α s2 + α 1d , β 2 + 1} < min{α s1 , α 2d } ∩ O c where O := {β 2 = 0, α s2 + α 1d ≤ 1} ∪ {α 1d = 0, β 2 + 1 ≤ α s2 } ∪ {α s2 = 0, β 2 + 1 ≤ α 1d }, that is, for max{1, α s2 , α 1d } < min{α s1 , α 2d } except in region O (16)
Case 2): if not in Case 1, then we are in

either α s1 ≥ α s2 α 1d < α 2d or α s1 < α s2 α 1d ≥ α 2d .
Consider the case α s2 ≤ α s1 , α 1d < α 2d (the other one is obtained essentially by swapping the role of the relays). This corresponds to an 'asymmetric' situation where relay 1 has the best link from the source but relay 2 has the best link to the destination. In this case we would like to exploit the inter relay communication links (which are not present in a diamond network) to create a route source→relay1→relay2→destination in addition to the direct link source→destination. Indeed, in this case d

(FD)
N =2 in ( 14) can be rewritten as

d (FD) N =2 = min max {α s2 + α 1d , β 2 + 1} , max{1, min{α s1 , α 2d }} , (17)
where the term max{1, min{α s1 , α 2d }} in ( 17) corresponds to the gDoF of a virtual single-relay channel such that the link from the source to the "virtual relay" has SNR-exponent α s1 and the link from the "virtual relay" to the destination has SNR-exponent α 2d . We aim to determine the subset of the channel parameters α s2 ≤ α s1 , α 1d < α 2d for which the gDoF in [START_REF] Gastpar | On the capacity of large Gaussian relay networks[END_REF] is strictly larger than the 'best relay' gDoF in [START_REF] Sanderovich | Communication via decentralized processing[END_REF]. The case α s2 ≤ α s1 , α 1d < α 2d subsumes the following possible orders of the channel gains:

case i α 1d α 2d α s2 α s1 case ii α 1d α s2 α 2d α s1 case iii α 1d α s2 α s1 α 2d case iv α s2 α 1d α 2d α s1 case v α s2 α 1d α s1 α 2d case vi α s2 α s1 α 1d α 2d
We partition the set of channel parameters α s2 ≤ α s1 , α 1d < α 2d as follows:

• Sub-case 2a) (all but cases i and vi in the table): if

max{α s2 , α 1d } < min{α s1 , α 2d }, (18) then d
(FD) N =2,best relay = max{1, α s2 , α 1d }, (19)
which is strictly less than d [START_REF] Ong | On the capacity of the binarysymmetric parallel-relay network[END_REF], at the top of the page, holds.

(FD) N =2 in (17) if
• Sub-case 2b) (case i in the table above): if α 1d < α 2d ≤ α s2 ≤ α s1 , then the condition is never verified, i.e., in this case d

d (FD) N =2,best relay = max{1, α 2d } < d (FD) N =2 = min max {α s2 + α 1d , β 2 + 1} , max{1, α 2d } Source Destination Relay1 α s1 = x α 1d = y ≥ 0 β 1 = z 1 α 2d = x>y α s2 = y Relay2 β 2 = z
(FD) N =2,best relay = d (FD) N =2 . • Sub-case 2c) (case vi in the table above): if α s2 ≤ α s1 ≤ α 1d < α 2d , then d (FD) N =2,best relay = max{1, α s1 } < d (FD) N =2
= min max {α s2 + α 1d , β 2 + 1} , max{1, α s1 } is never verified, i.e., in this case d

(FD) N =2,best relay = d (FD)
N =2 . To summarize, for a 2-relay network where the relays operate in FD, using both relays gives a strictly larger gDoF compared to only exploiting the best one if

max{1, α s2 , α 1d } < min{α s1 , α 2d } except for (20a) O := {β 2 = 0, α s2 + α 1d ≤ 1} ∪ {α 1d = 0, β 2 + 1 ≤ α s2 } ∪ {α s2 = 0, β 2 + 1 ≤ α 1d }. (20b)
Recall that there is also a regime similar to [START_REF] Niesen | Approximate capacity of the Gaussian nrelay diamond network[END_REF] where the role of the relays is swapped.

Fig. 4 gives an example of a network satisfying the conditions in [START_REF] Chern | Achieving the capacity of the n-relay Gaussian diamond network within log(n) bits[END_REF], i.e., the assumption is 0 ≤ y < x without loss of generality. This is an 'asymmetric' network, i.e., one relay has the best link from the source and the other relay has the best link to the destination. By exploiting both relays, the system attains d (FD) N =2 = min max{1, x, y}, max{2x, z + 1}, max{2y, z + 1} = min max{1, x}, max{2y, z + 1} , while, by using only the best relay, it achieves

d (FD) N =2,best relay = max 1, min{x, y} = max 1, y .
For future reference, if only one relay helps the communication between the source and the destination then the achievable gDoF is [START_REF] Cardone | The capacity to within a constant gap of the Gaussian half-duplex relay channel[END_REF]

d (HD) N=2,best relay = 1+ max i∈[1:2] [α si -1] + [α id -1] + [α si -1] + +[α id -1] + ∈ [1, d (HD) N=2 ]. (23)
An analytical closed form solution for the optimal {λ s } in ( 22) is complex to find for general channel gain assignments. However, numerically it is a question of solving a LP, for which efficient numerical routines exist. By using Theorem 4, we can set either λ 00 or λ 11 to zero.

For the example in Fig. 4 the optimal schedule has λ 00 = λ 11 = 0 without loss of optimality, from Theorem 4. By letting λ 01 = γ ∈ [0, 1] and λ 10 = 1γ (recall 0 ≤ y < x without N =2,best relay in [START_REF] Ong | On capacity and optimal scheduling for the half-duplex multiple-relay channel[END_REF] for different values of z ∈ [0, 3] in Fig. 4 and for x = 1.3, y = 0.4, 1.2. loss of generality), the gDoF in ( 22) can be written as

d (HD) N=2 = max γ∈[0,1] min γ max{1, x}+(1-γ) max{1, y}, (24a) γ max{2x, z + 1} + (1 -γ), (24b) γ
+ (1 -γ) max{2y, z + 1} (24c) = 1+min [x-1] + max{2y-1, z} [x-1] + +max{2y-1, z}-[y-1] + , (24d) max{2x -1, z} max{2y -1, z} max{2x -1, z} + max{2y -1, z} . (24e)
By using only the best relay as in [START_REF] Brahma | Simple schedules for halfduplex networks[END_REF], we would achieve

d (HD) N =2,best relay = 1 + [x -1] + [y -1] + [x -1] + + [y -1] + . (25)
It can be easily seen that the best relay selection policy is strictly suboptimal if ( 21) is verified, as for the FD case. Considerations similar to those made for the FD case, can be made for the HD case as well. Fig. 5 shows, for different values of z, i.e., strength of the links between the two relays, the behaviors of d N =2 in [START_REF] Brahma | On the structure of approximately optimal schedules for half-duplex diamond networks[END_REF]. Regarding the curves with y = 0.4, since we have y < 1 2 and hence max{2y -1, z} = z, ∀z ≥ 0, d 24) is an increasing function of z. On the other hand, since y < 1, d (HD) N =2,best relay in [START_REF] Ong | On capacity and optimal scheduling for the half-duplex multiple-relay channel[END_REF] is always equal to 1, i.e., direct transmission is gDoF optimal. We also notice that for z = 0, the two curves overlap since the condition in (21) holds. Regarding the curves with y = 1.2, we notice that d 24) is always strictly greater than d (HD) N =2,best relay in [START_REF] Ong | On capacity and optimal scheduling for the half-duplex multiple-relay channel[END_REF], i.e., the channel conditions are such that the synergies between the two relays bring to an unbounded rate gain with respect to best relay selection. Moreover, d (HD) N =2 in (24) starts to increase with z, when min {max{2y -1, z}, max{2x -1, z}} = max{2y -1, z} = z, i.e., z = 1.4 and best relay selection is always gDoF-wise greater than direct transmission, i.e., d

(HD) N =2 in (
(HD) N =2 in (
(HD) N =2,best relay > 1, since min{x, y} > 1. C multicast ⊇ i∈A R i ≤ I(X A ; Y A c |X A c , S [1:K] , Q) -I(Y A ; Y A | Y A c , X [1:K] , S [1:K] , Q) such that A ⊆ [1 : K], A = ∅, A c ∩ D = ∅ (26) C multicast ⊇    i∈A R i ≤ s∈[0:1] K λ s log I |A c | + 1 1 + σ 2 H A,s H H A,s -|A| log 1 + 1 σ 2 such that A ⊆ [1 : K], A = ∅, A c ∩ D = ∅ (27)

VI. CONCLUSIONS

In this work we analyzed a network where a source communicates with a destination across a Gaussian channel and is assisted by N relays operating in half-duplex mode. We characterized the capacity to within a constant gap by using noisy network coding as achievable scheme. We also showed that this gap may be further reduced by considering more structured systems, such as the diamond network. We conjectured that the optimal schedule has at most N +1 active states, instead of the possible 2 N . This conjecture has been supported by the analytical proof in the special case of N = 2 relays and in general by numerical evaluations. We finally analyzed a network with N = 2 relays, and we showed under which channel conditions by exploiting both relays a strictly greater gDoF can be attained compared to a network where best-relay selection is used.

An interesting connection between the high-SNR approximation of the point-to-point MIMO capacity and the Maximum Weighted Bipartite Matching problem from graph theory has been discovered.

APPENDIX A GAP RESULT FOR GAUSSIAN MULTICAST HD NETWORKS AND PROOF OF THEOREM 1

Here we slightly change the notation compared to the channel model introduced in Section II-B. In particular, for notation convenience, we number the nodes from 1 to K, rather than from 0 to N + 1. We aim to obtain a constant gap result for this class of networks that only depends on K, the total number of nodes, and for which the way the nodes are numbered is irrelevant.

A. Channel Model

A multicast network with K nodes is defined similarly to the multi-relay network introduced in Section II-B except that now each node k ∈ We let C multicast be the capacity region.

B. Inner Bound

The capacity of a HD Gaussian multicast network can be lower bounded by adapting the NNC scheme for the general memoryless network from [START_REF] Lim | Noisy network coding[END_REF] to the HD case by following the approach of [START_REF] Kramer | Models and theory for relay channels with receive constraints[END_REF]. In particular, NNC achieves the rate region [START_REF] Burkard | Assignment Problems[END_REF] at the top of the page, where Y k represents a compressed version of Y k , for k ∈ [1 : K], and where the union is over all input distributions that factorize as

P Q K k=1 P X k ,S k |Q P Y k |Y k ,X k ,S k ,Q
and satisfy the power constraints. We consider jointly Gaussian inputs so as to get a rate region similar to [13, eq.(20)]. In all states s ∈ [0 : 1] K , we consider i.i.d. N (0, 1) inputs, time sharing random variable Q set to Q = S [1:K] (with this choice the nodes can coordinate), and compressed channel output

Y k := Y k + Z k , k ∈ [1 : K],
for Z k ∼ N (0, σ 2 ) independent of all other random variables and where the variance of Z k does not depend on the user index k. With this the NNC achievable region evaluates to [START_REF] Kuhn | The Hungarian method for the assignment problem[END_REF] at the top of the page, where the union is over all λ s := P[S [1:K] = s] ∈ [0, 1], ∀s ∈ [0 : 1] K : s∈[0:1] K λ s = 1 and over all σ 2 ∈ R + , and where the matrix

H A,s ∈ C |A c |×|A| is defined as H A,s := (I K -diag[s]) H diag[s] A c ,A .

C. Outer Bound

The cut-set upper bound, adapted to the HD case by following [START_REF] Kramer | Models and theory for relay channels with receive constraints[END_REF], gives [START_REF] Gamal | Network Information Theory[END_REF] at the top of the next page, where the union is over all joint input distributions P X K ,S K and satisfy the power constraints. Similarly to [13, eq.( 19)], we upper bound each mutual information term as

I(X A , S A ; Y A c |X A c , S A c ) = I(S A ; Y A c |X A c , S A c ) + I(X A ; Y A c |X A c , S [1:K] ) ≤H(S A ) + s∈[0:1] K λ s log I |A c | + H A,s K A,s H H A,s (31a) ≤ |A| log(2) + s∈[0:1] K λ s log I |A c | + 1 γ H A,s H H A,s + s∈[0:1] K λ s |A| log e max 1, γ e |A| rank[H A,s ] max e γ , |A| rank[H A,s ] , (31b)
where: (i) K A,s represents the covariance matrix of X A conditioned on S [1:K] = s; (ii) the inequality in (31a) follows

C multicast ⊆ i∈A R i ≤ I(X A , S A ; Y A c |X A c , S A c ) such that A ⊆ [1 : K], A = ∅, A c ∩ D = ∅ (28) C multicast ⊆    i∈A R i ≤ |A| log(2) + s∈[0:1] K λ s log I |A c | + 1 γ H A,s H H A,s +|A| log e max 1, γ e |A| min{|A|,|A c |} max e γ , |A| min{|A|,|A c |} such that A ⊆ [1 : K], A = ∅, A c ∩ D = ∅    (29) GAP K ≤ min γ≥e-1 max µ∈[0,1] µ log 2γ γ -1 +µ min γ e ,

D. Gap

We now proceed to bound the worst case gap (over A) between the cut-set upper bound in [START_REF] Zhang | Study of Gaussian relay channels with correlated noises[END_REF] and the NNC lower bound in [START_REF] Kuhn | The Hungarian method for the assignment problem[END_REF] (recall that the parameters γ and σ 2 can be chosen so as to tighten the bound). By choosing σ 2 = γ -1 in [START_REF] Kuhn | The Hungarian method for the assignment problem[END_REF] and by defining µ = |A| K ∈ [0, 1], the gap is given by (30) at the top of the page, where the inequality in (30b) follows by numerical evaluations.

E. The HD multi-relay network

The unicast Gaussian network with HD relays is a special multicast network with K = N + 2 nodes (i.e., one source, N relays, and one destination). With a single source, the inner bound in [START_REF] Kuhn | The Hungarian method for the assignment problem[END_REF] allows to evaluate R (in) in (3), while the upper bound in (29) allows to evaluate R (out) in (3). From (30b) with K = N + 2 nodes we deduce that the GAP in (3) for the HD multi-relay network is as in [START_REF] Van Der Meulen | Three-terminal communication channel[END_REF].

The difference between the HD and the FD case is the factor 2 in (30a) for the HD case. Also notice that the HD gap of 1.96 bits/node is smaller than (1 + 1.26) bits/node where 1.26 bits/node is the FD gap [START_REF] Lim | Noisy network coding[END_REF] and the extra 1 bit/node is due to random switch.

APPENDIX B PROOF OF THEOREM 2

Let S n,k be the set of all k-combinations of the integers in [1 : n] and P n,k be the set of all k-permutations of the integers in [1 : n]. Let σ(π) be the sign / signature of the permutation π.

We start by demonstrating that the asymptotic behavior of |I k + HH H | is as that of |HH H |, i.e., the identity matrix can be neglected. By using the determinant Leibniz formula [START_REF] Broida | A comprehensive Introduction to Linear Algebra[END_REF], in fact we have,

|I k + HH H | = π∈P n,k σ(π) k i=1 I k + HH H i,π(i) = π∈P n,k σ(π) k i=2 I k +HH H i,π(i) I k +HH H 1,π(1) = π∈P n,k σ(π) k i=2 I k + HH H i,π(i) δ[1 -π(1)] + π∈P n,k σ(π) k i=2 I k + HH H i,π(i) HH H 1,π(1) . Let A (SNR) := π∈P n,k σ(π) k i=2 I k + HH H i,π(i) δ[1 -π(1)] B (SNR) := π∈P n,k σ(π) k i=2 I k + HH H i,π(i) HH H 1,π (
|HH H | (a) = ς∈S n,k |H ς ||H H ς | = ς∈S n,k |H ς | 2 (b) = ς∈S n,k π∈P n,k σ(π) k i=1 [H ς ] i,π(i) 2 = ς∈S n,k      π1∈P n,k σ(π 1 ) k i=1 [H ς ] i,π1(i)     π2∈P n,k σ(π 2 ) k j=1 [H ς ] j,π2(j)   *    = ς∈S n,k      π∈P n,k k i=1 [H ς ] i,π(i) 2   +   π1,π2∈P n,k ,π1 =π2 σ(π 1 )σ(π 2 ) k i=1 k j=1 [H ς ] i,π1(i) [H ς ] j,π2(j) *      (c) ≤ ς∈S n,k      π∈P n,k k i=1 [H ς ] i,π(i) 2   +   π1,π2∈P n,k ,π1 =π2 k i=1 k j=1 [H ς ] i,π1(i) 2 [H ς ] j,π2(j) 2      = ς∈S n,k      π∈P n,k SNR k i=1 [Bς ] i,π(i)   +   π1,π2∈P n,k ,π1 =π2 SNR 1 2 ( k i=1 [Bς ] i,π 1 (i) + k j=1 [Bς ] j,π 2 (j) )      (d) . = ς∈S n,k   π∈P n,k SNR k i=1 [Bς ] i,π(i)   . = SNR max ς∈S n,k max π∈P n,k k i=1 [Bς ] i,π(i) (32)
reasoning holds ∀i ∈ [1 : k] and hence

|I k + HH H | . = π∈P n,k σ(π) k i=1 HH H i,π(i) = |HH H |.
Therefore, we now focus on the study of |HH H |. We have that [START_REF] Gamal | Lecture notes on network information theory[END_REF], at the top of the page, holds, where the equalities / inequalities above are due to the following facts:

• equality (a): by applying the Cauchy-Binet formula [START_REF] Broida | A comprehensive Introduction to Linear Algebra[END_REF] where H ς is the square matrix obtained from H by retaining all rows and those columns indexed by ς; • equality (b): by applying the determinant Leibniz formula [START_REF] Broida | A comprehensive Introduction to Linear Algebra[END_REF]; • inequality (c): by applying the Cauchy-Schwarz inequality [START_REF] Steele | The Cauchy-Schwarz Master Class: an introduction to the art of mathematical inequalities[END_REF];

• equality (d): when SNR → ∞, we have k i=1 [B ς ] i,π(i) ≥ 1 2   k i=1 [B ς ] i,π1(i) + k j=1 [B ς ] j,π2 (j)
  .

Consider the following example. Let

|a| 2 = SNR βa , |b| 2 = SNR β b , |c| 2 = SNR βc , |d| 2 = SNR β d |ab -cd| 2 ≤ |a| 2 |b| 2 + |c| 2 |d| 2 + 2|a||b||c||d|.
Now apply the gDoF formula, i.e.,

d := lim SNR→+∞ log |a| 2 |b| 2 + |c| 2 |d| 2 + 2|a||b||c||d| log(1 + SNR) = max β a + β b , β c + β d , β a + β b + β c + β d 2 , but β a + β b + β c + β d 2 ≤ 2 max {β a + β b , β c + β d } 2 = max {β a + β b , β c + β d } .
Therefore, the term βa+β b +βc+β d 2 does not contribute in characterizing the gDoF. By direct induction, the above reasoning may be extended to a general number of terms leading to

k i=1 [B ς ] i,π(i) ≥ 1 2 k i=1 [B ς ] i,π1(i) + k j=1 [B ς ] j,π2(j) .

APPENDIX C PROOF OF THEOREM 4

In a HD relay network with N = 2, we have 2 N = 4 possible states that may arise with probabilities λ s , ∀s ∈ [0 : 1] 2 , with λ s = P[S [1:2] = s] ≥ 0, such that s∈[0:1] 2 λ s = λ 00 + λ 01 + λ 10 + λ 11 = 1. Here we aim to demonstrate that a schedule with λ 00 λ 11 = 0 is optimal.

We start by solving a fairly general LP, which we will then specialize to the gDoF case as well as to the case of a general finite SNR. is the optimal solution with λ (opt) 00

A. General LP

> 0. This implies that for any (α, β, γ) ∈ [0, 1] 3 such that α + β + γ = 1 we must have that [START_REF] Prabhakaran | Interference channels with source cooperation[END_REF], at the top of the next page, holds. Since λ (opt) 00 > 0 by assumption, we can rewrite the above problem as in [START_REF] Wang | Interference mitigation through limited transmitter cooperation[END_REF] at the top of the next page, for all (α, β, γ) ∈ [0, 1] 3 such that α + β + γ = 1.

If we can find a triplet (α, β, γ) ∈ [0, 1] 3 : α + β + γ = 1 for which [START_REF] Kannan | Approximately optimal wireless broadcasting[END_REF], at the top of the next page, holds we reach a contradiction; hence, for this set of values we must have λ

0 = min            max{a 1 , a 2 } + D 1 a 2 a 1 0 a 2 a 2 + b 1 + D 2 0 b 1 a 1 0 a 1 + b 2 + D 3 b 2 0 b 1 b 2 max{b 1 , b 2 } + D 4         1 0 0 0            ≥ min            max{a 1 , a 2 } + D 1 a 2 a 1 0 a 2 a 2 + b 1 + D 2 0 b 1 a 1 0 a 1 + b 2 + D 3 b 2 0 b 1 b 2 max{b 1 , b 2 } + D 4         0 α β γ            = min            a 2 a 1 0 a 2 + b 1 + D 2 0 b 1 0 a 1 + b 2 + D 3 b 2 b 1 b 2 max{b 1 , b 2 } + D 4       α β γ          (35)
α = b 2 a 2 + b 2 , β = b 1 a 1 + b 1 , γ = 1 -α -β = a 1 a 2 -b 1 b 2 (a 1 + b 1 )(a 2 + b 2 )
which is a valid assignment since all coefficients are nonnegative and sum to one. With this we have that [START_REF] Broida | A comprehensive Introduction to Linear Algebra[END_REF], at the top of the next page, holds. Hence, for b 1 b 2 ≤ a 1 a 2 and (a 1 , a 2 , b 1 , b 2 ) = (0, 0, 0, 0) we must have λ = 0, without loss of optimality. This is because, under these conditions, one of the constraints in [START_REF] Lovasz | Matching Theory[END_REF] becomes redundant and therefore, by contradiction, it is easy to show that either λ

C. The cut-set upper bound cast in the form of the general LP for gDoF

If one is interested in the gDoF for the Gaussian noise case, it suffices to consider d ≤ 1 + eq.( 33), which is the high-SNR approximation of [START_REF] Steele | The Cauchy-Schwarz Master Class: an introduction to the art of mathematical inequalities[END_REF] where the direct link from the source to the destination has SNR-exponent normalized 1, i.e., |h 33 | 2 = SNR 1 , without loss of generality. In this case the different quantities in (33) can be simply found by evaluating the different mutual information terms above and by using the definition in [START_REF] Everett | Empowering fullduplex wireless communication by exploiting directional diversity[END_REF]. We obtain

a ′ 2 = c ′ 2 = a 2 := [α s2 -1] + , a ′ 1 = d ′ 1 = a 1 := [α s1 -1] + , b ′ 1 = c ′ 1 = b 1 := [α 1d -1] + , b ′ 2 = d ′ 2 = b 2 := [α 2d -1] + , D 1 := 0, D 2 := max {α 1d + α s2 -1, β 2 } -[α 1d -1] + -[α s2 -1] + , D 3 := max {α 2d + α s1 -1, β 1 } -[α 2d -1] + -[α s1 -1] + , D 4 := 0,
where α si is the SNR-exponent on the link from the source to relay i, i ∈ [1 : 2], α id is the SNR-exponent on the link from relay i, i ∈ [1 : 2], to the destination and β i is the SNRexponent on the link from relay j to relay i, (i, j) ∈ [1 : 2] 2 with j = i.

Fig. 1 :

 1 Fig.1: Gap in (5) (solid curve) and gap in (6) (dashed curve) for the HD Gaussian relay network. The gap in (5) is smaller than that in (6) for any N ≥ 2.

Fig. 2 :

 2 Fig.2: Gap in (5) (dash-dotted curve), gap in (5) specialized to the HD diamond network (solid curve) and gap in[START_REF] Brahma | On the structure of approximately optimal schedules for half-duplex diamond networks[END_REF] (dashed curve) for the HD diamond network.

A 1

 1 consisting of k = |A 1 | = 1 node and the other set of vertices A 2 consisting of n = |A 2 | ≥ 1 nodes. The weights of the edges connecting the single vertex in A 1 to the n vertices in A 2 can be represented as the non-negative vector B = [β 1 , . . . , β n ]. Clearly, the optimal MWBM(B) = max i∈[1:n] {β i } assigns the single vertex in A 1 to the vertex in A 2 that is connected to it through the edge with the maximum weight.

ββ 31 β 34 β

 34 11 β 12 β 13 β 14 β 21 β 22 β 23 β 24 β 31 β 32 β 33 β 34 β 41 β 42 β 43 β 44 41 β 44 = max {β 31 + β 44 , β 34 + β 41 } .

Fig. 3 :

 3 Fig.3: Average, minimum and maximum number of active states to characterize the capacity of a HD relay network.

Fig. 4 :

 4 Fig. 4: Example of a two-relay network.

N

  Fig. 5: d (HD) N =2 in (24) and d (HD)

N

  =2,best relay in (25) and d (HD)

  [1 : K], with channel input (X k , S k ) and channel output Y k , has an independent message of rate R k to be decoded by the nodes indexed by D ⊆ [1 : K]. The channel input/output relationship of this HD Gaussian multicast network reads Y = (I K -diag[S]) H diag[S] X+Z.

e

  |A| rank[H A,s ] = γ e |A| min{|A|,|A c |} , from which it thus follows that (29), at the top of the page, holds, where the union is over all λ s := P[S [1:K] = s] ∈ [0, 1], ∀s ∈ [0 : 1] K :s∈[0:1] K λ s = 1 and where the parameter γ ≥ e -1 can be chosen to tighten the right hand side of[START_REF] Zhang | Study of Gaussian relay channels with correlated noises[END_REF].

  Consider the LP in[START_REF] Lovasz | Matching Theory[END_REF] at the top of the next page, where the different quantities (a u , b u ), u ∈ [1 : 2], and D v , v ∈ [1 : 4], are non-negative and will be defined later.The proof is by contradiction. Assume that λ

max{a 1 , a 2 } + D 1 a 2 a 1 0 a 2 a 2 + b 1 + D 2 0 b 1 a 1 0 a 1 + b 2 + D 3 b 2 0 b 1 b 2 max{b 1 , b 2 } + D 4 

 1221124

Assume b 1 b 2 ≤

 2 a 1 a 2 and define

  A similar reasoning shows that if b 1 b 2 ≥ a 1 a 2 and (a 1 , a 2 , b 1 , b 2 ) = (0, 0, 0, 0) we must have λ (opt) 11 = 0. It is easy to show that if min {a 1 , a 2 } = 0 then λ (opt) 00 = 0, without loss of optimality. Similarly if min {b 1 , b 2 } = 0 then λ (opt) 11

11 = 0 > 0

 1100 is optimal.B. The cut-set upper bound cast in the form of the general LP for a finite SNRFrom our previous discussion, we restrict attention to the case min {a 1 , a 2 , b 1 , b 2 } = 0. After straightforward manipulations the cut-set bound, for N = 2, can be further upper bounded as[START_REF] Steele | The Cauchy-Schwarz Master Class: an introduction to the art of mathematical inequalities[END_REF] at the top of the next page, where the termmax S1,S2 {I(X s ; Y d |X 1 , X 2 , S 1 , S 2 )} ≤ log(1 + |h 33 | 2 )and wherea ′ 2 := I(X 3 ; Y 2 |Y 3 , X 1 , X 2 , S 1 = 0, S 2 = 0), c ′ 2 := I(X 3 ; Y 2 |Y 3 , X 1 , X 2 , S 1 = 1, S 2 = 0), a ′ 1 := I(X 3 ; Y 1 |Y 3 , X 1 , X 2 , S 1 = 0, S 2 = 0), d ′ 1 := I(X 3 ; Y 1 |Y 3 , X 1 , X 2 , S 1 = 0, S 2 = 1), a 2 := max{a ′ 2 , c ′ 2 }, a 1 := max{a ′ 1 , d ′ 1 }, b ′ 1 := I(X 1 ; Y 3 |X 2 , S 1 = 1, S 2 = 1), c ′ 1 := I(X 1 ; Y 3 |X 2 , S 1 = 1, S 2 = 2), b ′ 2 := I(X 2 ; Y 3 |X 1 , S 1 = 1, S 2 = 1), d ′ 2 := I(X 2 ; Y 3 |X 1 , S 1 = 0, S 2 = 1) max (α,β,γ)∈[0,1] if (a 1 , a 2 , b 1 , b 2 ) = (0, 0, 0, 0)(37)R (cut-set,N =2) ≤ 2 log(2) + max S1,S2 {I(X s ; Y d |X 1 , X 2 , S 1 , S 2 )} + eq.(33)(38)andb 1 := max{b ′ 1 , c ′ 1 }, b 2 := max{b ′ 2 , d ′ 2 }, D 1 := I(X 3 ; Y 1 , Y 2 |Y 3 , X 1 , X 2 , S 1 = 0, S 2 = 0)+ max {I(X 3 ; Y 1 |Y 3 , X 1 , X 2 , S 1 = 0, S 2 = 0), I(X 3 ; Y 2 |Y 3 , X 1 , X 2 , S 1 = 0, S 2 = 0)} , D 2 := I(X 1 ; Y 2 |Y 3 , X 2 , S 1 = 1, S 2 = 0), D 3 := I(X 2 ; Y 1 |Y 3 , X 1 , S 1 = 0, S 2 =1), D 4 := I(X 1 , X 2 ; Y 3 |S 1 = 1, S 2 = 1)+ max {I(X 1 ; Y 3 |X 2 , S 1 = 1, S 2 = 1), I(X 2 ; Y 3 |X 1 , S 1 = 1, S 2 = 1)} .

  H ς and B ς are the square matrices obtained from H and B, respectively, by retaining all rows and the columns indexed by ς, and T is the sum of terms that overall behave as o SNRMWBM(B) .

  The corresponding MWBM problem has one set of vertices A 1 consisting of k = |A 1 | = 2 nodes (for future references let us refer to these vertices as nodes 1 and 2 -see first subscript in the channel gains) and the other set of vertices A 2 consisting also of n = |A 2 | = 2 nodes (for future references let us refer to these vertices as nodes 3 and 4 -see second subscript in the channel gains). The weights of the edges connecting the vertices in A 1 to the vertices in A 2 can be represented as the non-negative weights β

	23 h 14 h 24	=	SNR β13 e jθ13 SNR β14 e jθ14	SNR β23 e jθ23 SNR β24 e jθ24
	=⇒ B :=	β 13 β 23 β 14 β 24	,
	log I 2 + HH H	SNR≫1 . = log SNR max{β13+β24,β23+β14} .

ji , i ∈ [3 : 4], j ∈ [1

: 2]

. In this example, one possible matching assigns node 1 to node 3 and node 2 to node 4 (giving total weight β 13 + β 24 ), while the other possible matching assigns node 2 to node 3 and node 1 to node 4 (giving total weight β 23 + β 14 ); the best assignment is the one that gives the largest total weight.

  β 11 β 12 β 13 β 14 β 21 β 22 β 23 β 24 β 31 β 32 β 33 β 34 β 41 β 42 β 43 β 44

The k-combinations and the k-permutations of the integers in [1 : n] are defined as sequences of a fixed length k of elements taken from a given set of size n such that no elements occurs more than once. Then, over this k-length sequence all the possible combinations S n,k and all the possible permutations P n,k are computed. With π(i) we indicate the element in the i-th position of the permutation π ∈ P n,k .

s research is partially supported by its industrial partners: BMW Group Research & Technology, IABG, Monaco Telecom, Orange, SAP, SFR, ST Microelectronics, Swisscom and Symantec. The research at Eurecom leading to these results has received funding from the EU Celtic+ Framework Program Project SHARING. The work of D. Tuninetti was partially funded by NSF under award number 0643954; the contents of this article are solely the responsibility of the author and do not necessarily represent the official views of the NSF. The research work carried out at Intel by U. Salim has received funding from the EU FP7 grant agreement iJOIN n • 317941. M. Cardone would like to thank Paul de Kerret for insightful discussions.

By [START_REF] Ong | On the capacity of the binarysymmetric parallel-relay network[END_REF], we have d

Note that a non-zero link between relay1 and re-lay2 allows to route the information through the path source→relay1→relay2→destination, which leads to an increase in terms of gDoF with respect to the best relay selection strategy.

B. The half-duplex case

With HD, the gDoF is given by [START_REF] Özgür | Approximately achieving Gaussian relay network capacity with lattice-based QMF codes[END_REF], which with the notation in [START_REF] Lim | Noisy network coding[END_REF] becomes

where the maximization is over His current research and teaching interests are in the area of digital communications, software radio architectures, and implementation aspects of signal processing systems and real-time wireless networking protocols. He has a proven track record in managing both fundamental and experimental research projects at an international level and is also technical coordinator of the OpenAirInterface.org open-source wireless radio platform initiative which aims to bridge the gap between cutting-edge theoretical advances in wireless communications and practical designs.

Umer Salim received the Ph.D. and M.S. degrees, both in electrical engineering with specialization in communication theory and signal processing from EURECOM, France, and Supelec, France, respectively. He has several years of research experience in digital communications and signal processing and has published several papers in well-known conferences and journals. His mains areas of interest include signal processing techniques for multi-cell multiuser MIMO systems, novel and practical CSI feedback design techniques and analysis, information theoretic analysis of cognitive radio, and multi-user information theory in general. He has been serving as the reviewer for IEEE Trans. on Information Theory, IEEE Trans. on Wireless Communications, IEEE Trans. on Signal Processing and numerous well-known conferences. Dr. Salim co-authored a paper which received the best paper award at the European Wireless Conference 2011. Dr. Salim is currently working at Intel in the department of Systems engineering where the main focus is on the design of advanced receivers for future wireless standards. At Intel, he has designed sophisticated interference cancellation algorithms which are in use in modern high-end smart-phones and tablets.