2+ε approximation algorithm for the k-MST problem

For any ε>0, an n^O(1/ε) time algorithm that computes a 2+ε approximation to the k-MST problem is presented. A simple modification to Garg's three-approximation algorithms was used, through an linear programming and the primal-dual framework. It is noted that Garg had exhibited a `tight' instance for the approach, thus suggesting that three is the best approximation ratio achievable using the approach.