The average complexity of a coin-weighing problem

DOI10.1002/(SICI)1098-2418(199608/09)9:1/2%3C1::AID-RSA1%3E3.0.CO;2-0zbMATH Open0856.68070OpenAlexW2032903176MaRDI QIDQ4894598FDOQ4894598

Authors: L. Alonso, Philippe Chassaing, R. Schott 

Publication date: 7 October 1996

Full work available at URL: https://doi.org/10.1002/(sici)1098-2418(199608/09)9:1/2%3C1::aid-rsa1%3E3.0.co;2-0

Recommendations

• Minimal average cost of searching for a counterfeit coin: restricted model
• Coins with Arbitrary Weights
• Search for a majority element
• Searching for a counterfeit coin with \(b\)-balance

zbMATH Keywords

martingaleaverage complexityquasi-optimal algorithm

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10)

Cited In (6)

• Search for a majority element
• Coin-Weighing Problems
• Determining the majority: The biased case
• A balance scale problem
• On the Black-Box Complexity of Optimally-Fair Coin Tossing
• Lower Bounds for Coin-Weighing Problems

This page was built for publication: The average complexity of a coin-weighing problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4894598)