Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to non-federal websites. Their policies may differ from this site.
-
This paper considers a generalized version of the coin weighing problem with a spring scale that lies at the intersection of group testing and compressed sensing problems. Given a collection of n ≥ 2 coins of total weight d (for a known integer d), where the weight of each coin is an unknown integer in the range of {0, 1, ..., k} (for a known integer k ≥ 1), the goal is to determine the weight of each coin by weighing subsets of coins in a spring scale. The problem is to devise a weighing strategy that minimizes the average number of weighings over all possible weight configurations. For d = k = 1, an adaptive bisecting weighing strategy is known to be optimal. However, even the simplest non-trivial case of the problem, i.e., d = k = 2, is still open. For this case, we propose and analyze a simple and effective adaptive weighing strategy. Our analysis shows that the proposed strategy requires about 1.365log2n-0.5 weighings on average. As n grows unbounded, the proposed strategy, when compared to an optimal strategy within the commonly-used class of nested strategies, requires about 31.75% less number of weighings on average; and in comparison with the information-theoretic lower bound, it requires at most about 8.16% extra number of weighings on average.more » « less