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
\(T\subseteq V\) containing a root
\(r\in T\), a cost function
\(c:E\rightarrow \mathbb {R}^+\), a length function
\(\ell :E\rightarrow \mathbb {R}^+\), a bound
\(L>0\) and an integer
\(k\ge 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
\(T\subseteq V\) containing a root
\(r\in T\), cost and length functions
\(c,\ell :E\rightarrow \mathbb {R}^+\), and an integer
\(k\ge 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 n\cdot \text{ opt }^*)\) where
\(\text{ opt }^*\) is the cost of an LP relaxation of the problem and diameter at most
\(O(L\cdot \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).