# Approximating some network design problems with node costs

Guy Kortsarz, Zeev Nutov

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء

## ملخص

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.

اللغة الأصلية الإنجليزيّة Approximation, Randomization, and Combinatorial Optimization Algorithms and Techniques - 12th International Workshop, APPROX 2009 and 13th International Workshop, RANDOM 2009, Proceedings 231-243 13 https://doi.org/10.1007/978-3-642-03685-9_18 نُشِر - 2009 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2009 and 13th International Workshop on Randomization and Computation, RANDOM 2009 - Berkeley, CA, الولايات المتّحدةالمدة: ٢١ أغسطس ٢٠٠٩ → ٢٣ أغسطس ٢٠٠٩

### سلسلة المنشورات

الاسم Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 5687 LNCS 0302-9743 1611-3349

### !!Conference

!!Conference 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2009 and 13th International Workshop on Randomization and Computation, RANDOM 2009 الولايات المتّحدة Berkeley, CA ٢١/٠٨/٠٩ → ٢٣/٠٨/٠٩

## بصمة

أدرس بدقة موضوعات البحث “Approximating some network design problems with node costs'. فهما يشكلان معًا بصمة فريدة.