\input zb-basic
\input zb-ioport
\iteman{io-port 05674260}
\itemau{Segev, Danny; Segev, Gil}
\itemti{Approximate $k$-Steiner forests via the Lagrangian relaxation technique with internal preprocessing.}
\itemso{Algorithmica 56, No. 4, 529-549 (2010).}
\itemab
Summary: An instance of the $k$-Steiner forest problem consists of an undirected graph $G=(V,E)$, the edges of which are associated with non-negative costs, and a collection $\mathcal{D}=\{(s_{1},t_{1}),\dots,(s_{d},t_{d})\}$ of distinct pairs of vertices, interchangeably referred to as demands. We say that a forest $\Cal F\subseteq G$ connects a demand $(s _{i },t _{i })$ when it contains an $s _{i }-t _{i }$ path. Given a profit $k _{i }$ for each demand $(s _{i },t _{i })$ and a requirement parameter $k$, the goal is to find a minimum cost forest that connects a subset of demands whose combined profit is at least $k$. This problem has recently been studied by {\it M. Hajiaghayi} and {\it K. Jain} [``The prize-collecting generalized Steiner tree problem via a new approach of primal-dual schema'', in: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, Miami, FL, January 22--24, 2006. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). 631--640 (2006; Zbl 1192.90228)], whose main contribution in this context was to relate the inapproximability of $k$-Steiner forest to that of the dense $k$ -subgraph problem. However, Hajiaghayi and Jain did not provide any algorithmic result for the respective settings, and posed this objective as an important direction for future research.  In this paper, we present the first non-trivial approximation algorithm for the $k$-Steiner forest problem, which is based on a novel extension of the Lagrangian relaxation technique. Specifically, our algorithm constructs a feasible forest whose cost is within a factor of $O(\min \{n^{2/3},\sqrt{d}\}\cdot \log d)$ of optimal, where $n$ is the number of vertices in the input graph and $d$ is the number of demands. We believe that the approach illustrated in the current writing is of independent interest, and may be applicable in other settings as well.
\itemrv{~}
\itemcc{}
\itemut{approximation algorithms; Lagrangian relaxation; Steiner forest; dense $k$-subgraph}
\itemli{doi:10.1007/s00453-008-9189-8}
\end