Min k-vertex cover: Given a graph $G = (V,E)$, the goal of the min k-vertex cover problem is to output $k$ vertices from $V$ such that the number of uncovered edges in $E$ is minimized.
It is easy to see that this problem is inapproximable unless studied in a bi-criteria setting. We know a very simple LP-rounding algorithm for this problem that is a $(3,3)$ bi-criteria approximation.
Q. Has this problem been studied in the literature elsewhere, perhaps with a different name? Are there any known combinatorial approximation algorithms for this problem?
Clarification: The objective of this problem is to output a set of vertices $S$ that minimize the number of uncovered edges in $G = (V,E)$. The number of uncovered edges is equal to the number of edges in $E$ that have neither end point in $S$.