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
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 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, ארצות הברית
משך הזמן: 21 אוג׳ 200923 אוג׳ 2009

סדרות פרסומים

שםLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
כרך5687 LNCS
ISSN (מודפס)0302-9743
ISSN (אלקטרוני)1611-3349

כנס

כנס12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2009 and 13th International Workshop on Randomization and Computation, RANDOM 2009
מדינה/אזורארצות הברית
עירBerkeley, CA
תקופה21/08/0923/08/09

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Approximating some network design problems with node costs'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי