  The classical problem of maximizing a submodular function under a matroid
constraint is considered. Defining a new measure for the increments made by the
greedy algorithm at each step, called the discriminant, improved approximation
ratio guarantees are derived for the greedy algorithm. At each step,
discriminant measures the multiplicative gap in the incremental valuation
between the item chosen by the greedy algorithm and the largest potential
incremental valuation for eligible items not selected by it. The new guarantee
subsumes all the previous known results for the greedy algorithm, including the
curvature based ones, and the derived guarantees are shown to be tight via
constructing specific instances. More refined approximation guarantee is
derived for a special case called the submodular welfare maximization/partition
problem that is also tight, for both the offline and the online case.
