How to prove the local search algorithm can find the maximum weight independent set in a matroid with cardinality constraint?

Question

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 return the optimal solution. But the author did not provide a proof.

I tried to follow the greedy algorithm heuristic 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.

Answer 1

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|$.