shakil.ahamed's blog

By shakil.ahamed, history, 6 years ago, In English

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.

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by shakil.ahamed (previous revision, new revision, compare).