A (log23 + 12) competitive algorithm for the counterfeit coin problem

✍ Scribed by Peng-Jun Wan; Ding-Zhu Du

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 912 KB
• Volume: 163
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(95)00314-m

✦ Synopsis

Consider a set of coins where each coin is either of the heavy type or the light type. The problem is to identify the type of each coin with minimal number of weighings on a balanced scale. The case that only one coin, called a counterfeit, has a different weight from others, is a classic mathematical puzzle. Later works study the case of more than one counterfeit, but the number of counterfeits is always assumed known. Recently, Hu and Hwang gave an algorithm which does not depend on the knowledge of the number of counterfeits, and yet perform uniformly good whatever that number turns out to be in the sample considered. Such an algorithm is known as a competitive algorithm and the uniform guarantee is measured by its competitive constant. Their algorithm has competitive ratio 21og23. In this paper, we give a new competitive algorithm with competitive ratio log 2 3 + ½.