2018/05/08 by Esmaeil Karimi, Karimi, Esmaeil, Fatemeh Kazemi +5
Computer Science · Engineering · Mathematics · Medicine · #Advancements in Photolithography Techniques #Combinatorics #Computer science #Discrete mathematics #FOS: Computer and information sciences #Information Theory (cs.IT) #Integer (computer science) #Intersection (aeronautics) #Machine Learning and Algorithms #Mathematical analysis #Mathematical optimization #Mathematics #Range (aeronautics) #SARS-CoV-2 detection and testing #Scale (ratio) #Simple (philosophy) #Upper and lower bounds #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.1805.02977
10 pages, 3 figures; A shorter version will appear in ISIT 2018
arxiv created 2018/05/08 · openalex publication_date 2018/05/08 · arxiv updated 2018/05/09 · openalex created_date 2022/10/01 · openalex updated_date 2026/08/05
This paper considers a generalized version of the coin weighing problem with\na spring scale that lies at the intersection of group testing and compressed\nsensing problems. Given a collection of n\≥ 2 coins of total weight d\n(for a known integer d), where the weight of each coin is an unknown integer\nin the range of 0,1,\…,k (for a known integer k\≥ 1), the problem\nis to determine the weight of each coin by weighing subsets of coins in a\nspring scale. The goal is to minimize the average number of weighings over all\npossible weight configurations. For d=k=1, an adaptive bisecting weighing\nstrategy is known to be optimal. However, even the case of d=k=2, which is\nthe simplest non-trivial case of the problem, is still open. For this case, we\npropose and analyze a simple and effective adaptive weighing strategy. A\nnumerical evaluation of the exact recursive formulas, derived for the analysis\nof the proposed strategy, shows that this strategy requires about 1.365\log2\nn -0.5 weighings on average. To the best of our knowledge, this is the first\nnon-trivial achievable upper bound on the minimum expected required number of\nweighings for the case of d=k=2. As n grows unbounded, the proposed\nstrategy, when compared to an optimal strategy within the commonly-used class\nof nested strategies, requires about 31.75 % less number of weighings on\naverage; and in comparison with the information-theoretic lower bound, it\nrequires at most about 8.16 % extra number of weighings on average.\n