1
$\begingroup$

Let $(X,d)$ be a metric space and $a,b\in X^n$ be two arrays of elements of $X$. Define $ \rho(a,b):=\inf\limits_{\sigma\in \Sigma}\sup\limits_{1\leq i\leq n}d(a_i,b_{\sigma(i)}) $ where the $\inf$ is taken over all possible permutations $\sigma$ of the set $\{1,\dots,n\}$. I wonder, how given a matrix of positive reals $\rho_{ij} = d(a_i,b_j)$ to find $\rho$ in a fast way.

In case this question better fits more CS-oriented website, please close it - I ask it on stackoverflow.

1 Answers 1

1

You can model this as a graph problem. You have a bipartite graph $G$, with $2n$ vertices $\{a_1,a_2,\ldots, a_n,b_1,b_2,\ldots b_n\}$. You connect every vertex $a_i$ with every vertex $b_j$. Moreover, you give every edge $(a_i,b_j)$ the weight $\rho_{ij}$. A permutation $\sigma$ corresponds now to a perfect matching in $G$.

Let me first discuss how to solve the decision problem for your question, that is you ask if $M:=\inf_{\sigma\in \Sigma} \sup_{1\le i\le n} \rho_{i,\sigma(i)}\le k.$ You first delete all edges that have too large weights, i.e., all edges $(a_i,b_j)$ with $\rho_{ij}>k$. If there exists a perfect matching in the remaining graph, then $M$ is less then $k$, otherwise not. You can decide if a perfect matching exists by the algorithm of Hopcroft and Kahn (other algorithms are also applicable).

Since you have now an alogorithm for the decision problem you can simply run a binary search over all possible solutions, which are the weights $\rho_{ij}$.

PS I think than cs.SE is a good place for these type of questions.