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 costs Multicommodity Buy at Bulk (MBB) problem in which we are given a graph G = (V,E), demands {d _st : s,t ∈ V}, and a family {c _v : v ∈ V} of subadditive cost functions. For every s,t ∈ V we seek to send d _st flow units from s to t on a single path, so that ∑ _v c _v (f _v) is minimized, where f _v the total amount of flow through v. In the Multicommodity Cost-Distance (MCD) problem we are also given lengths {ℓ(v):v ∈ V}, and seek a subgraph H of G that minimizes c(H) + ∑ _{s,t ∈ V} d _st · ℓ _H (s,t), where ℓ _H (s,t) is the minimum ℓ-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 ³ 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 ⁴ 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 ³ h to log ² 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(v):v ∈ V}, profits {p(v):v ∈ 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) = Ω(opt/log n). We provide the first nontrivial 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 Ω(1/(log log n)) approximation assuming NP ⊈ Quasi(P) even if the algorithm is allowed to violate the budget by any universal constant ρ. 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(v):v ∈ V}, lengths {ℓ(v):v ∈ V}, a set U ⊆ V of terminals, and a bound L. The goal is to find a subtree T of G containing U with diam _ℓ(T) ≤ L and c(T) minimum. We give an algorithm that computes a tree T with c(T) = O(log ² n) · opt and diam _ℓ(T) = O(log n) · L.. Previously, a polylogarithmic bicriteria approximation was known only for the case of edge costs and edge lengths.