  We revisit a classical problem in transportation, known as the continuous
(bilevel) network design problem, CNDP for short. We are given a graph for
which the latency of each edge depends on the ratio of the edge flow and the
capacity installed. The goal is to find an optimal investment in edge
capacities so as to minimize the sum of the routing cost of the induced Wardrop
equilibrium and the investment cost. While this problem is considered as
challenging in the literature, its complexity status was still unknown. We
close this gap showing that CNDP is strongly NP-complete and APX-hard, both on
directed and undirected networks and even for instances with affine latencies.
  As for the approximation of the problem, we first provide a detailed analysis
for a heuristic studied by Marcotte for the special case of monomial latency
functions (Mathematical Programming, Vol.~34, 1986). Specifically, we derive a
closed form expression of its approximation guarantee for arbitrary sets S of
allowed latency functions. Second, we propose a different approximation
algorithm and show that it has the same approximation guarantee. As our final
-- and arguably most interesting -- result regarding approximation, we show
that using the better of the two approximation algorithms results in a strictly
improved approximation guarantee for which we give a closed form expression.
For affine latencies, e.g., this algorithm achieves a 1.195-approximation which
improves on the 5/4 that has been shown before by Marcotte. We finally discuss
the case of hard budget constraints on the capacity investment.
