  This paper studies the 1-2-1 half-duplex network model, where two half-duplex
nodes can communicate only if they point `beams' at each other; otherwise, no
signal can be exchanged or interference can be generated. The main result of
this paper is the design of two polynomial-time algorithms that: (i) compute
the approximate capacity of the 1-2-1 half-duplex network and, (ii) find the
network schedule optimal for the approximate capacity. The paper starts by
expressing the approximate capacity as a linear program with an exponential
number of constraints. A core technical component consists of building a
polynomial-time separation oracle for this linear program, by using algorithmic
tools such as perfect matching polytopes and Gomory-Hu trees.
