For two point sets A,B ⊂ Rd, with |A| = |B| = n and d > 1 a constant, and for a parameter ϵ> 0, we present a randomized algorithm that, with probability at least 1/2, computes in O(n(ϵ-O(d3) log log n + ϵ-O(d) log4 n log5 log n)) time, an ϵ-approximate minimum-cost perfect matching under any Lp-metric. All previous algorithms take n(ϵ-1 log n)ω(d) time. We use a randomly-shifted tree, with a polynomial branching factor and O(log log n) height, to define a tree-based distance function that ϵ-approximates the Lp metric as well as to compute the matching hierarchically. Then, we apply the primal-dual framework on a compressed representation of the residual graph to obtain an efficient implementation of the Hungarian-search and augment operations.