Pergunta

Many people on different articles suggests that if an optimization problem has a greedy solution, the underlying structure must have matroid property.

I was trying to understand this. So far, I was able to prove that for,

  1. Maximum sum of m integers among n integer.
  2. Minimum spanning tree.

However, The classical greedy algorithm Activity Selection seems to fail having both independence and base exchange property.

Let, E = {1-3, 2-4, 3-5, 4-6, 5-7}

Now, Take two independent set, I = {2-4, 4-6} and J = {1-3, 3-5, 5-7}

There is no activity in J which can extend I. Which fails the independence exchange property of matroid, if I understood it correctly. Thus, it is not matroid and shouldn't have a greedy algorithms. But this problem has a greedy solution.

Where am I wrong?

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top