  In this paper, we introduce the problem of Matroid-Constrained Vertex Cover:
given a graph with weights on the edges and a matroid imposed on the vertices,
our problem is to choose a subset of vertices that is independent in the
matroid, with the objective of maximizing the total weight of covered edges.
This problem is a generalization of the much studied max $k$-vertex cover
problem, in which the matroid is the simple uniform matroid, and it is also a
special case of the problem of maximizing a monotone submodular function under
a matroid constraint.
  First, we give a Fixed-Parameter Tractable Approximation Scheme (FPT-AS) when
the given matroid is a partition matroid, a laminar matroid, or a transversal
matroid. Precisely, if $k$ is the rank of the matroid, we obtain $(1 -
\varepsilon)$ approximation using $(1/\varepsilon)^{O(k)}n^{O(1)}$ time for
partition and laminar matroids and using $(1/\varepsilon+k)^{O(k)}n^{O(1)}$
time for transversal matroids. This extends a result of Manurangsi for uniform
matroids [Manurangsi, 2018]. We also show that these ideas can be applied in
the context of (single-pass) streaming algorithms. Besides, our FPT-AS
introduces a new technique based on matroid union, which may be of independent
interest in extremal combinatorics.
  In the second part, we consider general matroids. We propose a simple local
search algorithm that guarantees $2/3 \approx 0.66$ approximation. For the more
general problem where two matroids are imposed on the vertices and a feasible
solution must be a common independent set, we show that a local search
algorithm gives a $2/3 \cdot (1 - 1/(p+1))$ approximation in $n^{O(p)}$ time,
for any integer $p$. We also provide some evidence to show that with the
constraint of one or two matroids, the approximation ratio of $2/3$ is likely
the best possible, using the currently known techniques of local search.
