optimization – sub-optimal and quick solutions to the problem of assignment

I am looking for a quick solution to the assignment problem for high cost matrices (5000×5000 or more). The Hungarian algorithm is $ O ^ 3 $, which is not practical for any medium size problem.
Are there similar algorithms but suboptimal and fast, possibly in R (or in Python)?

The problem I'm working on is finding the best pairs of points in sets A and B (| A | = | B |), minimizing their overall distance.