Buy-at-bulk network design: approximating the single-sink edge installation problem
F. Sibel Salman, Joseph Cheriyan, R. Ravi, Sairam Subramanian · 1997
We initiate the algorithmic study of an important but NP-hard problem that arises commonly in network design. The input consists of (1) An undirected graph with one sink node and multiple source nodes, a specified length for each edge, and a specified demand, dem{sub v}, for each source node v. (2) A small set of cable types, where each cable type is specified by its capacity and its cost per unit length. The cost per unit capacity per unit length of a high-capacity cable may be significantly less than that of a low-capacity cable, reflecting an economy of scale, i.e., the payoff for buying at bulk may be very high.