Abstract: The weighed matching problem asks for a subset of edges of a weighted graph such that no two edges are incident on the same vertex and such that the sum of the weight of the selected edges is as high as possible.This problem pops up in a number of scientific applications including sparse linear algebra. Although there exists polynomial time exact algorithms for this problem these are often too time consuming to be used on large problems. In this talk we first review the status of efficient approximation algorithms for weighted matching. We then present new sequential as well as multicore algorithms for this problem. We first give a one-phase sequential algorithm that is shown to be faster than the current fastest 0.5-approximation algorithms on sparse graphs. This is then extended to a two-phase algorithm that is both faster and gives better matchings than the current best linear time heuristics for this problem. Finally, we show that both of our algorithms are easily parallelizable on multicore computers. A number of experiments on different architectures verifies our claims and shows that the algorithms scale better than previous efforts at designing shared memory matching algorithms.