Improved approximations for buy-at-bulk and shallow-light $$k$$ k -Steiner trees and $$(k,2)$$ ( k , 2 ) -subgraph

In this paper we give improved approximation algorithms for some network design problems. In the bounded-diameter or shallow-light $$k$$ k -Steiner tree problem (SL $$k$$ k ST), we are given an undirected graph $$G=(V,E)$$ G = ( V , E ) with terminals $$T\subseteq V$$ T ⊆ V containing a root $$r\in T$$ r ∈ T , a cost function $$c:E\rightarrow \mathbb {R}^+$$ c : E → R + , a length function $$\ell :E\rightarrow \mathbb {R}^+$$ ℓ : E → R + , a bound $$L>0$$ L > 0 and an integer $$k\ge 1$$ k ≥ 1 . The goal is to find a minimum $$c$$ c -cost $$r$$ r -rooted Steiner tree containing at least $$k$$ k terminals whose diameter under $$\ell $$ ℓ metric is at most $$L$$ L . The input to the buy-at-bulk $$k$$ k -Steiner tree problem (BB $$k$$ k ST) is similar: graph $$G=(V,E)$$ G = ( V , E ) , terminals $$T\subseteq V$$ T ⊆ V containing a root $$r\in T$$ r ∈ T , cost and length functions $$c,\ell :E\rightarrow \mathbb {R}^+$$ c , ℓ : E → R + , and an integer $$k\ge 1$$ k ≥ 1 . The goal is to find a minimum total cost $$r$$ r -rooted Steiner tree $$H$$ H containing at least $$k$$ k terminals, where the cost of each edge $$e$$ e is $$c(e)+\ell (e)\cdot f(e)$$ c ( e ) + ℓ ( e ) · f ( e ) where $$f(e)$$ f ( e ) denotes the number of terminals whose path to root in $$H$$ H contains edge $$e$$ e . We present a bicriteria $$(O(\log ^2 n),O(\log n))$$ ( O ( log 2 n ) , O ( log n ) ) -approximation for SL $$k$$ k ST: the algorithm finds a $$k$$ k -Steiner tree with cost at most $$O(\log ^2 n\cdot \text{ opt }^*)$$ O ( log 2 n · opt ∗ ) where $$\text{ opt }^*$$ opt ∗ is the cost of an LP relaxation of the problem and diameter at most $$O(L\cdot \log n)$$ O ( L · log n ) . This improves on the algorithm of Hajiaghayi et al. (2009) (APPROX’06/Algorithmica’09) which had ratio $$(O(\log ^4 n), O(\log ^2 n))$$ ( O ( log 4 n ) , O ( log 2 n ) ) . Using this, we obtain an $$O(\log ^3 n)$$ O ( log 3 n ) -approximation for BB $$k$$ k ST, which improves upon the $$O(\log ^4 n)$$ O ( log 4 n ) -approximation of Hajiaghayi et al. (2009). We also consider the problem of finding a minimum cost $$2$$ 2 -edge-connected subgraph with at least $$k$$ k vertices, which is introduced as the $$(k,2)$$ ( k , 2 ) -subgraph problem in Lau et al. (2009) (STOC’07/SICOMP09). This generalizes some well-studied classical problems such as the $$k$$ k -MST and the minimum cost $$2$$ 2 -edge-connected subgraph problems. We give an $$O(\log n)$$ O ( log n ) -approximation algorithm for this problem which improves upon the $$O(\log ^2 n)$$ O ( log 2 n ) -approximation algorithm of Lau et al. (2009).