# 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$$.