Approximate Maximum Weight Matching
You should try Sage's implementation. It uses LP, but I don't think that you would get something so large in less than 100milliseconds. Greedy probabilistic would be nice in this case I guess.

http://www.sagemath.org/doc/reference/graphs/sage/graphs/graph.html#sage.graphs.graph.Graph.matching