4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Have you tried it? Have you tried writing a little program to try a million test cases and see if you can find a counterexample? Have you tried proving it correct? $\endgroup$ – D.W. Aug 5 '16 at 16:54
  • 1
    $\begingroup$ @D.W. You are right. A simple example was sufficient to prove that my algorithm was wrong. $\endgroup$ – Erel Segal-Halevi Aug 7 '16 at 4:39
  • 1
    $\begingroup$ Can you edit the question a bit more? The edit "tag" makes it hard to see what the real question is. (There's first a question, and then another one later on). $\endgroup$ – Juho Aug 7 '16 at 6:15
  • $\begingroup$ The largest size of an independent set contains in a set $S$ is known as the rank of $S$. Whether it is easy to compute might depend on the matroid. $\endgroup$ – Yuval Filmus Aug 8 '16 at 10:33
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.