Modeling the problem of hiring experts by a coalitional game a uniform lower bound on the performance of the greedy heuristic for a family of games can be specified.We show a uniform bound for this family holds when only approximate rather than exact values of coalitions are known.One of the prettiest applications of this general analysis is to the s-median problem.Approximation algorithms for the s-median problem are a useful tool in learning Lipschitz functions in the generalized PAC learning model ([8], [9]).To approximate a Lipschitz function a memory-based learning system can be used, as proposed by Lin and Vitter ([14]).We generalize the analysis of a greedy approximate solution of the s-median problem first considered by Comuejols et.al. ([4]).We then compare its performance to the performance of Lin and Vitter's linear programming approximate solution of the same problem as a tool in the construction of memory-based learning systems.We find the greedy approximation is simpler, more efficient and in many cases yields a smaller system.