Bi-criteria combinatorial approximation algorithms for min k-vertex cover 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$.
Partial Vertex Cover (PVC) solves the problem without the need for bi-criteria. In PVC the input is a graph $G=(V,E)$ and an integer $m' \le |E|$ and the goal is to find a minimum cardinality subset $S$ of vertices such that they cover at least $m'$ edges. Hence, if $m' = |E|$ we have the usual Vertex Cover problem. A $2$-approximation is known for PVC. To solve the OP's question, if we know the number of edges that are not covered by an optimum solution consisting of $k$ vertices (which we can guess), say $\ell$, we set $m' = |E| - \ell$ and run the approximation algorithm for PVC. We will obtain a set $S \subseteq V$ of cardinalty at most $2k$ such that no more than $\ell$ edges are uncovered.