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-0MaRDI QIDQ4894598zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

martingaleaverage complexityquasi-optimal algorithm

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10)

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

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)