Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer 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.

share|improve this answer
    
+1 and thanks, for an advise to ask it on cs.se –  Ilya Aug 23 '12 at 7:14
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.