  This paper studies networks with N half-duplex relays assisting the
communication between a source and a destination. In ISIT'12 Brahma,
\"{O}zg\"{u}r and Fragouli conjectured that in Gaussian half-duplex diamond
networks (i.e., without a direct link between the source and the destination,
and with N non-interfering relays) an approximately optimal relay scheduling
policy (i.e., achieving the cut-set upper bound to within a constant gap) has
at most N+1 active states (i.e., at most N+1 out of the $2^N$ possible relay
listen-transmit states have a strictly positive probability). Such relay
scheduling policies were referred to as simple. In ITW'13 we conjectured that
simple approximately optimal relay scheduling policies exist for any Gaussian
half-duplex multi-relay network irrespectively of the topology. This paper
formally proves this more general version of the conjecture and shows it holds
beyond Gaussian noise networks. In particular, for any memoryless half-duplex
N-relay network with independent noises and for which independent inputs are
approximately optimal in the cut-set upper bound, an approximately optimal
simple relay scheduling policy exists. A convergent iterative polynomial-time
algorithm, which alternates between minimizing a submodular function and
maximizing a linear program, is proposed to find the approximately optimal
simple relay schedule. As an example, for N-relay Gaussian networks with
independent noises, where each node in equipped with multiple antennas and
where each antenna can be configured to listen or transmit irrespectively of
the others, the existence of an approximately optimal simple relay scheduling
policy with at most N+1 active states is proved. Through a line-network example
it is also shown that independently switching the antennas at each relay can
provide a strictly larger multiplexing gain compared to using the antennas for
the same purpose.
