## Abstract

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 ^{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(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 ^{2} 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.

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

Title of host publication | Approximation, Randomization, and Combinatorial Optimization |

Subtitle of host publication | Algorithms and Techniques - 12th International Workshop, APPROX 2009 and 13th International Workshop, RANDOM 2009, Proceedings |

Pages | 231-243 |

Number of pages | 13 |

DOIs | |

State | Published - 2009 |

Event | 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2009 and 13th International Workshop on Randomization and Computation, RANDOM 2009 - Berkeley, CA, United States Duration: Aug 21 2009 → Aug 23 2009 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 5687 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2009 and 13th International Workshop on Randomization and Computation, RANDOM 2009 |
---|---|

Country/Territory | United States |

City | Berkeley, CA |

Period | 8/21/09 → 8/23/09 |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)

## Keywords

- Approximation algorithm
- Covering tree
- Hardness of approximation
- Multicommodity Buy at Bulk
- Network design
- Node costs