Approximating Some Network Design Problems with Node Costs

We study several multi-criteria undirected network design problems with node costs and lengths with all problems related to the node cost's Multicommodity Buy at Bulk (MBB) problem in which we are given a graph G = (V, E), demands {d(st) : s,t is an element of V} and a family {c(nu) : nu is an element of V} of subadditive cost functions. For every s,t is an element of V we seek to send d(st) flow units from s to t on a single path, so that Sigma(nu) c(nu)(f(nu)) is minimized, Where f(nu) the Lotal alliolint, of flow through nu. lit the Multicommodity Cost-Distance (MCD) problem we are also given lengths, {l(nu) : nu is an element of V}, and seek a subgraph H of G that minimizes c(H) + Sigma(s,t is an element of V) d(st) . l(H)(s,t), where l(H)(s,t) is the minimum l-length of an st-path in H. The approximation for these two problems is equivalent, up to a factor arbitrarily close to 2. We give an O(log(3) n)-approximation algorithm for both problems for the case of demands, polynomial in n. The previously best. known approximation ratio for these problems was O(log(4) n) [Chekuri et; al, FOCS 2006] and [Chekuri et al., SODA 2007]. This technique seems quite robust, and was already used in order to improve, the ratio of Buy-at-bulk with protection (Antonakopoulos et, al FOCS 2007) from log(3) h to log(2) h. See [3]. We also consider the Maximum Covering Tree (MaxCT) problem which is closely related to MBB: given a, graph G = (V,E), costs {c(nu) : nu is an element of V}, profits {p(nu) : nu is an element of V}, and a bound C, find a subtree T of G with c(T) <= C and p(T) maximum. The best, known approximation algorithm for MaxCT [Moss and Rabani, STOC 2001] computes a tree T with c(T) <= 2C and p(T) = Omega(opt/log n). We provide the first non-trivial lower bound and in fact. provide a bicriteria lower bound on approximating this problem (which is stronger than the usual lower bound) by showing that, the problem admits no better than Omega(1/(log log n)) approximation assuming NP not subset of Quasi(P) even if the algorithm is allowed to violate the budget by arty universal constant rho. This disproves a conjecture of [Moss and Rabani, STOC 2001]. Another related to MBB problem is the Shallow Light Steiner Tree (SLST) problem, in which we, are given a graph G = (V, E) costs {c(nu) : nu is an element of V} lengths {l(nu) : nu is an element of V}, a set, U subset of V of terminals, and a bound L. The goal is to find a subtree T of G containing U with diam(l)(T) : L and c(T) minimum. We give an algorithm that computes a tree T with c(T) O(log(2)n) . opt and diam(l)(T) = O(log n) . L. Previously a polylogarithmic bicriteria, approximation was known only for the case of edge costs and edge lengths.