Events

I consider decision problems of the following type: 'Given an instance of a combinatorial problem, can it be solved by a greedy algorithm?'.

If the answer is positive, the instance at hand is greedy. The precise meaning of 'a greedy algorithm' varies according to the combinatorial problem at hand. It   

always based, however, upon some 'best fits' or 'any which fits' approach, and it avoids backtracking. A greedy instance of a combinatorial problem is an

instance of that problem which can be solved by a greedy algorithm.

I'll present efficient algorithms for the recognition of greedy instances of certain combinatorial problems, structural characterization of such instances for other

problems, and proofs of NP-hardness of the recognition problem for other cases.