  In this paper, we study the $k$-forest problem in the model of resource
augmentation. In the $k$-forest problem, given an edge-weighted graph $G(V,E)$,
a parameter $k$, and a set of $m$ demand pairs $\subseteq V \times V$, the
objective is to construct a minimum-cost subgraph that connects at least $k$
demands. The problem is hard to approximate---the best-known approximation
ratio is $O(\min\{\sqrt{n}, \sqrt{k}\})$. Furthermore, $k$-forest is as hard to
approximate as the notoriously-hard densest $k$-subgraph problem.
  While the $k$-forest problem is hard to approximate in the worst-case, we
show that with the use of resource augmentation, we can efficiently approximate
it up to a constant factor.
  First, we restate the problem in terms of the number of demands that are {\em
not} connected. In particular, the objective of the $k$-forest problem can be
viewed as to remove at most $m-k$ demands and find a minimum-cost subgraph that
connects the remaining demands. We use this perspective of the problem to
explain the performance of our algorithm (in terms of the augmentation) in a
more intuitive way.
  Specifically, we present a polynomial-time algorithm for the $k$-forest
problem that, for every $\epsilon>0$, removes at most $m-k$ demands and has
cost no more than $O(1/\epsilon^{2})$ times the cost of an optimal algorithm
that removes at most $(1-\epsilon)(m-k)$ demands.
