The objective of this paper is to characterize classes of problems for which a greedy algorithm finds solutions provably close to optimum. To that end, we introduce the notion of k-extendible systems, a natural generalization of matroids, and show that a greedy algorithm is a 1/k-factor approximation for these systems. Many seemly unrelated problems fit in our framework, e.g.: b-matching, maximum profit scheduling and maximum asymmetric TSP. In the second half of the paper we focus on the maximum weight b- atching problem. The problem forms a 2-extendible system, so greedy gives us a 1/2 -factor solution which runs in O(m logn) time. We improve this by providing two linear time approximation algorithms for the problem: a 1/2 -factor algorithm that runs in O(b m) time, and a (2/3- e) -factor algorithm which runs in expected O(bm log 1/e) time.