linear programming – Randomized Assignment Problem


Given $x_1,…,x_n,y_1,…,y_nin mathbb{R}^d$ find a permutation matrix $Pinmathbb{S}_d$ that minimizes $sum_{ij}P_{ij}|x_i-y_j|$.

This is an assignment problem and can be solved in $O(n^3+n^2d)$ time using the Hungarian algorithm.

Suppose $x_isim N(0, I_d)$ and let $v=mathbb{E}_{S={x_1,…,x_n}}left(min_{Pinmathbb{S}_d} sum_{ij}|x_i-y_j|right)$. Does anyone know of an algorithm that can compute $v$?

I’m also interested in algorithms for other distributions, e.g., $x_isim U(0,1)^d$ or $x_isim L(0,1)^d$.