Approximating some network design problems with node costs

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 s t: s, t ∈ V }, and a family { c v: v ∈ V } of subadditive cost functions. For every s, t ∈ V we seek to send d s t flow units from s to t, so that ∑ v c v ( f v ) is minimized, where f v 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 s t -flow is unsplittable, namely, uses only one path. 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 s t ⋅ ℓ H ( s, t ), where ℓ H ( s, t ) is the minimum ℓ -length of an s t -path in H. The approximability of these two problems is equivalent up to a factor 2 − ε [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 ( 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 ) ≤ 2 C and p ( T ) = Ω ( opt / log n ). We provide the first nontrivial lower bound on approximation by proving that the problem admits no better than Ω ( 1 / ( log log n ) ) 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 ( 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.

Authors

• Guy Kortsarz
• Zeev Nutov

Keywords

• Network design
• Node costs
• Multicommodity buy at bulk
• Approximation algorithm