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. 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 cv:v∈V of subadditive cost functions. For every s,t∈V we seek to send dst flow units from s to t, so that ∑vcv(fv) is minimized, where fv 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∈Vdst·ℓ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(log3n)-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(log4n) (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(log2n)·opt and diam ℓ (T)=O(logn)·L. Previously, a polylogarithmic bicriteria approximation was known only for the case of edge costs and edge lengths.

שפה מקוריתאנגלית
עמודים (מ-עד)4482-4492
מספר עמודים11
כתב עתTheoretical Computer Science
מספר גיליון35
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 12 אוג׳ 2011

הערה ביבליוגרפית

Funding Information:
We thanks a referee for his/her insightful comments that significantly helped in improving the presentation of the paper. The first author was partially supported by NSF support grant award number 0829959.

טביעת אצבע

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

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