Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

In this paper, the authors mention that it is possible to get an $o(n^2)$-time algorithm for the nuts and bolts problem by choosing samples based on a projective plane. They also mention that a non-constructive $O(n^{1.5}\log n)$-time algorithm can be obtained (pages 2-3). They omit the details.

I am interested in understanding these approaches, although they are not optimal. Could someone please provide the details of how this is done?

share|improve this question
3  
(1) Have you asked the authors? (2) It's not clear that these algorithms are "easy"! –  JɛffE Feb 11 '13 at 17:06
    
(1) Not yet. (2) I meant 'easier'..I've edited the question. –  Plummer Feb 12 '13 at 5:10
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.