Algorithms for the Coin Weighing Problems with the Presence of Noise.
Nader H. Bshouty, Hanna Mazzawi · Electronic colloquium on computational complexity · 2011
The coin weighing problem is the following: Given n coins for which m of them are counterfeit with the same weight. The problem is to detect the counterfeit coins with minimal number of weighings. This problem has many applications in compressed sensing, multiple access adder channels, etc. This problem was solved when m is unknown. An old optimal non-adaptive polynomial time algorithm of Lindstrom does O(n/ log n) weighings can detect the counterfeit coins. In this paper we give a non-adaptive polynomial time algorithm that does O(n/ log n) weighings and detect the counterfeit coins even if n of the answers of the weighings received are incorrect or missing for any constant c < 1. When m is known we give an adaptive polynomial time algorithm that does O((m log n)/ log m) weighings and detect the counterfeit coins even if m of the answers of the weighings received are incorrect or missing for any constant c < 1. We then study the problem when m is known and the counterfeit coins have different weights. We show that there is an optimal non-adaptive algorithm for detecting the counterfeit coins with O((m log n)/log m) weighing even if 11 percent of the answers are incorrect or missing. A simple information theoretical argument shows that all the above algorithm are optimal.