Finding a maximum-weight base of a a matroid, in reverse

Question

Given a weighted matroid with positive weights, we can find a independent set with a maximum weight with a greedy algorithm:

• Start with an empty set (by definition of matroid, it is independent).
• Add an element with maximum weight among all elements whose addition keeps the current set independent (if there are no such elements, terminate).

My goal is to found out whether this approach can also work in reverse. My first attempt was:

• Start with a set containing all elements.
• As long as the set is NOT independent, remove the element with minimum weight.

This attempt proved to be false. Here is an example:

There are 8 elements, divided to two groups: A and B. The matroid contains all subsets that have at most two elements of each group. The weights are:

• Group A: 303,302,301,300.
• Group B: 203,202,201,200.

The forward-greedy approach picks 303, 302, 203, 202 - which is optimal. But the reverse-greedy approach removes 200,201,202,203,300,301, and leaves only 302,303.

But, I think the following alternative algorithm should work:

• Start with a set containing all elements.
• As long as the set is not independent, remove the element with minimum weight among all elements whose removal leaves a base in the current set.

So, in the above example, this algorithm removes 200 and 201, but does not remove 202 and 203 (since then no base will remain), then removes 300 and 301, and stops with the maximum-weight independent set.

I am not sure about the complexity of this algorithm. Particularly, how much time does it take to calculate whether the current set (after removing an element) contains a base?

Answer 1

Let $M$ be a matroid with non-negative weight function $w$ and rank function $r$ (the rank of a set of points $S \subseteq M$ is the maximal size of an independent subset of $S$). Suppose that the matroid has rank $m$. You propose the following algorithm:

1. $S = M$.
2. While $|S| > m$: remove from $S$ a minimum weight element $x$ such that $r(S-x) = m$.
3. Return $S$.

This algorithm clearly returns a base. Let $W(S)$ denote the maximum weight of an independent subset of $S$. We prove by induction on the steps of the algorithm that $W(S) = W(M)$. The base case is clear. For the inductive step, suppose that $S$ contains a base $B$ of weight $W(M)$, and suppose that we removed an element $x \in S$ to obtain the new set $S'$. If $x \notin B$ then clearly $W(S') = W(M)$. Otherwise, let $B'$ be a base contained in $S'$ (which exists by the definition of the algorithm). Since $|B'| > |B-x|$, there exists an element $y \in B' \setminus B$ such that $B'' = B-x+y$ is a base. By definition, $w(y) \geq w(x)$, and so $$W(S') \geq w(B'') = w(B)-w(x)+w(y) \geq w(B) = W(M),$$ completing the proof.

---

Answering your question, it is a classical result that the rank function can be computed efficiently using an independence oracle. Perhaps you can come up with the algorithm.