Activity Selection and Matroid Theory

Revision en3, by shakil.ahamed, 2018-03-10 10:47:54

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.

UPDATE
Well, I got the answer. In strict sense, the activity selection algorithm is called greedy-like not greedy. That is the reason. There are many algorithm which we take as greedy but they aren't greedy in mathematical sense. They are just greedy-like. This also explain how many people misguiding others that you should prove the matroid property when solve greedy problem. Fortunately, many people also suggest not to use matoroid as an criteria.

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)