How can you be sure that a problem exhibits "Greedy choice property"?

Question

I am afraid that there might be a situation for which the "greedy choice property" might not hold.

For any problem, I can only check for small data-sets. What if, for large data-sets, the property fails?

Can we ever be sure?

Answer 1

A probably more theoretical way is the proof that your problem has a Matroid structure. If you can proof that your problem has such a structure, there is a greedy algorithm to solve it.

According to the classical book "Introduction to Algorithms" a matroid a is an ordered pair M = (S,l) with:

* S is a finite nonemtpy set
* l is a nonempty family of subsets of S, such that B element of l and 
  A a subset of B than also A is element of l. l is called the independent 
  subsets of S.
* If A and B are elements of l and A is a smaller cardinality than B, then 
  there is some element x that is in B, but not in A, so that A extended 
  by x is also element of l. That is called exchange property.

Often there is also a weight function w that assigns each element x in S, a weight.

If you can formulate your function as weighted matroid that the following Python-like pseudocode solves your problem:

GREEDY(M,w):
   (S,l) = M
   a = {}
   sort S into monotonically decreasing order by weight w
   for x in S:
      if A + {x} in l:
         A = A + {x}