Structure Mapping Theory (SMT) is an important and influential theory in cognitive science. One unresolved issue is this theory's intractability. It is known that finding optimally systematic analogies under SMT is NP-hard, making it unrealistic that human analogizing is characterized by optimality. Yet, experimental studies suggest that the optimality assumption gives the best fit to human performance data. A solution to this paradox may be that SMT can be efficiently approximated to such a degree that, for practical intents and purposes, human analogies appear to be optimal. However, outside of a limited empirical evaluation of the commonly-used greedy SME heuristic given in Forbus and Oblinger (1990), no analyses of the approximability of SMT have been done to date. We fill this void by providing both the first theoretical analyses of the types of efficient approximability available for SMT and the first systematic empirical evaluation of the greedy SME heuristic.