I am trying to prove a simple local search algorithm could solve exactly this problem:


$\underset{S \in I(M), |S|=k}{max} c(S)$


where $M$ is a matroid, and $ I(M)$ is the set of all independent set, $c(S) = \sum\_{v \in S}c(v)$.


In the book "A First Course in Combinatorial Optimization" by Jon Lee, it is given that
a [local search/ Swap algorithm](https://i.stack.imgur.com/pTozj.png) return the optimal solution. But the author did not provide a proof.


I tried to follow the [greedy algorithm heuristic](https://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture15.pdf) to prove the optimality of this local search algorithm, but it didn't work.


I also tried to prove it when the matroid is a graphic matroid, e.g., a spanning tree. I tried to use the cycle property of the minimum spanning tree to prove the optimality, but it didn't work either.



How to prove the local search algorithm can find the maximum weight independent set in a matroid with cardinality constraint?
Let $I$ be the independent set of size $k$ returned by the local search algorithm. Thus, $c(J) \leq c(I)$ for every independent set $J$ of size $k$ such that $|I \Delta J|=2$. Towards a contradiction, suppose that $I$ is not a maximum weight independent set of size $k$. Among all maximum weight independent sets of size $k$, choose $I'$ such that $|I' \cap I|$ is maximum.


Let $x \in I \setminus I'$. Since $I$ and $I'$ are bases in the matroid obtained by truncating $M$ to rank $k$, by the symmetric basis exchange axiom, there exists $y \in I' \setminus I$ such that $(I \setminus x) \cup \{y\}$ and $(I' \setminus y) \cup \{x\}$ are both independent sets. If $c(y)>c(x)$, then $(I \setminus x) \cup \{y\}$ contradicts the stopping condition of local search. If $c(y) < c(x)$, then $(I' \setminus y) \cup \{x\}$ contradicts that $I'$ is a maximum weight independent set of size $k$. If $c(y)=c(x)$, then $(I' \setminus y) \cup \{x\}$ contradicts the maximality of $|I' \cap I|$.


