Improved approximation algorithms for the single-sink buy-at-bulk network design problems

Consider a given undirected graph G=(V,E)G=(V,E) with non-negative edge lengths, a root node r∈Vr∈V, and a set D⊆VD⊆V of demands   with dvdv representing the units of flow that demand v∈Dv∈D wishes to send to the root. We are also given K types of cables, each with a specified capacity and cost per unit length. The single-sink buy-at-bulk (SSBB) problem asks for a low-cost installation of cables along the edges of G, such that the demands can simultaneously send their flow to root r. The problem is studied with and without the restriction that the flow from a node must follow a single path to the root. We are allowed to install zero or more copies of a cable type on each edge. The SSBB problem is NP-hard. In this paper, we present a 153.6-approximation algorithm for the SSBB problem improving the previous best ratio of 216. For the case in which the flow is splittable, we improve the previous best ratio of 76.8 to αKαK, where αKαK is less than 67.94 for all K  . In particular, α2<17.7α2<17.7, α3<23.2α3<23.2, α4<28.8α4<28.8, and α5<34.3α5<34.3.