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.

The problem can be stated as the following:

Given a sequence of numbers $a_1, \ldots, a_n$ and $b_1, \ldots, b_n$ such that $\{b_i\}_{i=1}^{n}$ is a permutation of $\{a_i\}_{i=1}^{n}$, find an efficient algorithm which, using only comparisons between $a_i$ and $b_j$ for some $1 \le i, j \le n$, computes the permutation $\sigma$ satisfying $b_{\sigma(i)} = a_i$ for all $1 \le i \le n$.

It's easy to see that the efficiency is $\Omega(n \log{n})$ since the sorting problem can be reduced to this problem.

The original problem I saw allowed the algorithm to be randomized. By modifying quicksort algorithm a little bit we can find the optimal algorithm. (choose a pivot $a_i$, divide all $b_j$ by checking if $b_j$ is bigger/lesser/equal than $a_i$. again choose $b_{\sigma(i)}$ and do the same thing for $a_i$s, separate all lesser/bigger numbers and do the same thing recursively)

My question is that, if we restrict the algorithm to be only deterministic, can we still find the optimal algorithm for the problem?

Sorry for my short and flawed english :D

share|improve this question
    
What does it mean to restrict the algorithm to be only deterministic? Presumably the "randomized" algorithm uses a deterministic pseudo-random number generator? How would you distinguish a "deterministic" algorithm from such a "randomized" algorithm? –  joriki Jul 24 '11 at 9:57
    
Just to clarify, we're not allowed to (directly) compare $a_i$ with $a_j$, or $b_i$ with $b_j$, right? (If we can do that, it should be easy to reduce the problem back to sorting.) –  Ilmari Karonen Jul 24 '11 at 10:12
    
@joriki Sorry for confusion. What I mean by randomized algorithm is that it uses pure "ideal" random number generator and its efficiency for a input is measured by the expected value of the time taken by the algorithm. The "randomized" algorithm's efficiency is the maximum of efficiency for all inputs can be made. –  Jineon Baek Jul 24 '11 at 10:33
    
@joriki "deterministic" algorithm never uses a pure "ideal" random number generator. So it can use PRNG or whatsoever. However its efficiency is measured by the maximum of efficiency for all inputs can be made(efficiency for a input is measured by just time taken for that input). –  Jineon Baek Jul 24 '11 at 10:35
    
@Ilmari Karonen Sorry for confusion again. YES :-) –  Jineon Baek Jul 24 '11 at 10:36

1 Answer 1

up vote 3 down vote accepted

This problem is known as “matching nuts and bolts,” posed by Alon, Blum, Fiat, Kannan, Naor, and Ostrovsky [ABF+94]. It was solved by Komlós, Ma, and Szemerédi [KMS98], who gave a deterministic O(n log n)-time algorithm. This is optimal for the reason which you stated in the question.

[ABF+94] Noga Alon, Manuel Blum, Amos Fiat, Sampath Kannan, Moni Naor, and Rafail Ostrovsky. Matching nuts and bolts. In Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’94), pp. 690–696, 1994. http://portal.acm.org/citation.cfm?id=314673

[KMS98] János Komlós, Yuan Ma, and Endre Szemerédi. Matching nuts and bolts in O(n log n) time. SIAM Journal on Discrete Mathematics, 11(3):347–372, 1998. http://dx.doi.org/10.1137/S0895480196304982

share|improve this answer

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.