Consider a set of points and an associated demand for traffic between each pair of points. In this thesis, we consider the perspective of a notional Network Service Provider (NSP) that has to decide on which connections to build and which demands to satisfy to maximize its profits. The NSP makes these decisions based on the demand for connectivity and the constraints on the resources needed to provide those connections. ...