科研之友
微信
新浪微博
Facebook
分享链接
摘要
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 is an element of V}, and a family {C(nu) : nu is an element of V] of subadditive cost functions. For every s, t is an element of V we seek to send d(st) flow units from s to t, so that Sigma(nu) C(nu) (f(nu)) is minimized, where f(nu) is the total amount of flow through nu. It is shown in Andrews and Zhang (2002) [2] that with a loss of 2-epsilon in the ratio, we may assume that each st-flow is unsplittable, namely, uses only one path. In the Multicommodity Cost-Distance (MCD) problem we are also given lengths {l(nu) : nu is an element of V), and seek a subgraph H of G that minimizes c(H)+Sigma(s,t is an element of v) d(st).l(H)(s, t), where l(H)(s, t) is the minimum l-length of an st-path in H. The approximability of these two problems is equivalent up to a factor 2 - epsilon [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(nu) : nu is an element of V}, profits {p(nu) : nu is an element of 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) = Omega(opt/log n). We provide the first nontrivial lower bound on approximation by proving that the problem admits no better than Omega(1/(log log n)) approximation assuming NP not subset of Quasi(P). This holds true even if the solution is allowed to violate the budget by a constant rho, as was done in [18] with rho = 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(nu) : nu is an element of V), lengths {l(nu) : nu is an element of V}, a set U subset of V of terminals, and a bound L. The goal is to find a subtree T of G containing U with diam(l)(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(l)(T) = O(log n) . L. Previously, a polylogarithmic bicriteria approximation was known only for the case of edge costs and edge lengths.
- 出版日期2011-8-12
