An improved deterministic algorithm for generating different many-element random samples

✍ Scribed by Amihood Amir; Emanuel Dar

• Book ID: 104137383
• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 625 KB
• Volume: 62
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(97)00047-1

✦ Synopsis

We consider the problem of deterministically selecting s uniformly random different m-element subsets of { 1, . . . , k}. The only known lower bound for the time to solve this problem is the trivial a( sm). The best two previously known solutions are of time 0( sm3 log m log log m) and 0( s( k + m)), respectively. In this paper we present an algorithm whose time complexity is 0( s2m2 + snz* log m log log m + sm log sm). Thus, for s < m log m log log m this algorithm is the fastest known deterministic algorithm. The main idea of the algorithm is using a uniform random number generator to efficiently construct biased random numbers.