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.
↵
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.
