Buy-at-bulk network design

The essence of the simplest buy-at-bulk network design problem is buying network capacity “wholesale” to guarantee connectivity from all network nodes to a certain central network switch. Capacity is sold with “volume discount”: the more capacity is bought, the cheaper is the price per unit of bandwidth. We provide O(log²n) randomized approximation algorithm for the problem. This solves the open problem in Salman et al. (1997). The only previously known solutions were restricted to special cases (Euclidean graphs). We solve additional natural variations of the problem, such as multi-sink network design, as well as selective network design. These problems can be viewed as generalizations of the the Generalized Steiner Connectivity and Prize-collecting salesman (K-MST) problems. In the selective network design problem, some subset of κ wells must be connected to the (single) refinery, so that the total cost is minimized