A weighted, semi-discrete, fast optimal transport (OT) algorithm for reconstructing the Lagrangian positions of proto-halos from their evolved Eulerian positions is presented. The algorithm makes use of a mass estimate of the biased tracers and of the distribution of the remaining mass (the `dust'), but is robust to errors in the mass estimates. Tests with state-of-art cosmological simulations show that if the dust is assumed to have a uniform spatial distribution, then the shape of the OT-reconstructed pair correlation function of the tracers is very close to linear theory, enabling sub-percent precision in the BAO distance scale that depends weakly, if at all, on a cosmological model. With a more sophisticated model for the dust, OT returns an estimate of the displacement field which yields superb reconstruction of the proto-halo positions, and hence of the shape and amplitude of the initial pair correlation function of the tracers. This enables direct and independent determinations of the bias factor $b$ and the smearing scale $\Sigma$, potentially providing new methods for breaking the degeneracy between $b$ and $\sigma_8$.
Comment: matches published version (Physical Review Letters)