Activity Selection and Matroid Theory

Revision en2, by shakil.ahamed, 2018-03-07 10:57:00

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 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 exchange property of matroid, if I understood it correctly. Thus, it is not matroid and shouldn't have a greedy algorithms.

Where am I wrong?

NB:
1. a-b means starts at time a end just before time b.
2. I know matroid is not best way to find greedy algorithms in contest. I just like to understand the underlying structure once.

EDIT:
Please Suggest some math forum where I may get the answer.

Tags greedy, matroids

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English shakil.ahamed 2018-03-10 10:47:54 471 resolved
en2 English shakil.ahamed 2018-03-07 10:57:00 75
en1 English shakil.ahamed 2018-03-06 17:40:19 990 Initial revision (published)