## Abstract

We study several multi-criteria undirected network design problems with node costs and lengths. All these problems are related to the 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, so that ∑_{v}c_{v}(f_{v}) is minimized, where f_{v} is the total amount of flow through v. It is shown in Andrews and Zhang (2002) [2] that with a loss of 2-ε in the ratio, we may assume that each st-flow is unsplittable, namely, uses only one path. In the Multicommodity CostDistance (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 approximability of these two problems is equivalent up to a factor 2-ε[2]. We give an O(log^{3}n)-approximation algorithm for both problems for the case of the demands polynomial in n. The previously best known approximation ratio for these problems was O(log^{4}n) (Chekuri et al., 2006, 2007) [5,6]. 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, 2001) [18] computes a tree T with c(T)≤2C and p(T)=Ω(optlogn). We provide the first nontrivial lower bound on approximation by proving that the problem admits no better than Ω(1(loglogn)) approximation assuming NP⊈Quasi(P). This holds true even if the solution is allowed to violate the budget by a constant ρ, as was done in [18] with ρ=2. Our result disproves a conjecture of [18]. Another problem related to MBB 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^{2}n)·opt and diam ℓ (T)=O(logn)·L. Previously, a polylogarithmic bicriteria approximation was known only for the case of edge costs and edge lengths.

Original language | English (US) |
---|---|

Pages (from-to) | 4482-4492 |

Number of pages | 11 |

Journal | Theoretical Computer Science |

Volume | 412 |

Issue number | 35 |

DOIs | |

State | Published - Aug 12 2011 |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- General Computer Science

## Keywords

- Approximation algorithm
- Multicommodity buy at bulk
- Network design
- Node costs