Searching for a subset of counterfeit coins: Randomization vs determinism and adaptiveness vs non‐adaptiveness1. Issue 1 (4th April 2012)

• Record Type: Journal Article
• Authors: De Marco, Gianluca; Kowalski, Dariusz R.
• Is Part Of: Random structures & algorithms. Volume 42:Issue 1(2013)
• Page Start: 97
• Page End: 109
• Publication Date: 2012-04-04
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20417
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main" xml:lang="en"> <title>Abstract</title> <p>We are given <italic>n</italic> coins of which <italic>k</italic> are heavy (defective), while the remaining <italic>n</italic> ‐ <italic>k</italic> are light (good). We know both the weight of the good coins and the weight of the defective ones. Therefore, if we weigh a subset <italic>Q</italic> ⊆ <italic>S</italic> with a spring scale, then the outcome will tell us exactly the number of defectives contained in <italic>Q</italic>. The problem, known as <italic>Counterfeit Coins</italic> problem, is to identify the set of defective coins by minimizing the number of weighings, also called <italic>queries</italic>. It is well known that Θ(<italic>k</italic>log <sub><italic>k</italic> +1</sub>(<italic>n</italic>/<italic>k</italic>)) queries are enough, even for non‐adaptive algorithms, in case <italic>k</italic> ≤ <italic>c</italic><italic>n</italic> for some constant 0 < <italic>c</italic> < 1.</p> <p>A natural interesting generalization arises when we are required to identify any subset of <italic>m</italic> ≤ <italic>k</italic> defectives. We show that while for randomized algorithms <tex-math notation="LaTeX"><![CDATA[\documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}\tilde{\Theta}(m)\end{align*} \end{document}]]></tex-math><inline-graphic xlink:href="ark:/27927/pgg1fbccfd0" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /> queries are sufficient, the deterministic non‐adaptive counterpart still requires Θ(<italic>k</italic>log <sub><italic>k</italic> +1</sub>(<italic>n</italic>/<italic>k</italic>)) queries, in case <italic>k</italic> ≤ <italic>n</italic>/2<sup>8</sup>; therefore, finding any subset of defectives is not easier than finding all of them by a non‐adaptive deterministic algorithm. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012</p> </abstract>