Activity Selection and Matroid Theory
-
05-11-2019 - |
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,
- Maximum sum of m integers among n integer.
- 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