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

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