Given a graph $$G(V,E)$$ of order $$n$$ and a constant $$k \leqslant n$$ , the max $$k$$ -vertex cover problem consists of determining $$k$$ vertices that cover the maximum number of edges in $$G$$ . In its (standard) parameterized version, max $$k$$ -vertex cover can be stated as follows: "given $$G,$$ $$k$$ and parameter $$\ell ,$$ does $$G$$ contain $$k$$ vertices that cover at least $$\ell $$ edges?". We first devise moderately exponential exact algorithms for max $$k$$ -vertex cover, with time-complexity exponential in $$n$$ but with polynomial space-complexity by developing a branch and reduce method based upon the measure-and-conquer technique. We then prove that, there exists an exact algorithm for max $$k$$ -vertex cover with complexity bounded above by the maximum among $$c^k$$ and $$\gamma ^{\tau },$$ for some $$\gamma < 2,$$ where $$\tau $$ is the cardinality of a minimum vertex cover of $$G$$ (note that $${\textsc {max}}\,$$ k $${\textsc {\!-vertex cover}}{} \notin \mathbf{FPT}$$ with respect to parameter $$k$$ unless $$\mathbf{FPT} = \mathbf{W[1]}$$ ), using polynomial space. We finally study approximation of max $$k$$ -vertex cover by moderately exponential algorithms. The general goal of the issue of moderately exponential approximation is to catch-up on polynomial inapproximability, by providing algorithms achieving, with worst-case running times importantly smaller than those needed for exact computation, approximation ratios unachievable in polynomial time.