  The status quo of limited broadband connectivity in rural areas motivates the
need for fielding alternatives such as long-distance wireless mesh networks. A
key aspect of fielding wireless meshes cost-effectively is planning how to
connect the last-mile networks to the core network service providers (i.e., the
network between the edge access terminals and the landline / optical fiber
terminals) with minimal infrastructure cost and throughput constraints. This
so-called middle-mile network optimization, which includes topology
construction, tower height assignment, antenna and orientation selection, as
well as transmit power assignment, is known to be a computationally hard
problem.
  In this paper, we provide the first polynomial time approximation solution
for a generalized version of the middle-mile network optimization problem,
wherein point-to-point (i.e., WiFi p2p) links are deployed to bridge last-mile
networks. Our solution has a cost performance ratio of
$O(\ln{|A|}+\frac{|B|}{|A|}+\frac{|A|+|B|}{\gamma})$, where A and B
respectively denote the number of terminals and non-terminals and $\gamma$ is
the ratio of $\frac{link\ capacity}{terminal\ demand}$. Furthermore, our
solution extends to hybrid networks, i.e., point-to-multipoint (i.e., WiFi
p2mp) or omnidirectional (i.e., TV White Space) can serve as hyperlinks in
addition to point-to-point links, to further reduce the cost of wireless links.
We provide a complementary heuristic for our middle-mile network optimization
solution that adds hyperlinks if and only if they reduce the cost.
