✦ LIBER ✦

A 32log 3-competitive algorithm for the counterfeit coin problem

✍ Scribed by Peng-Jun Wan; Qifan Yang; Dean Kelley

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 524 KB
Volume: 181
Category: Article
ISSN: 0304-3975
DOI: 10.1016/s0304-3975(96)00279-4

No coin nor oath required. For personal study only.

✦ Synopsis

We study the following counterfeit coin problem: Suppose that there is a set of II coins. Each one is either heuuy or light. The goal is to sort them according to weight with a minimum number of weighings on a balance scale. Hu and Hwang gave an algorithm with a competitive ratio of 3 log 3 (all logarithms are base-2). Hu, Chen and Hwang also gave an algorithm with a competitive ratio of 2 log 3. In this paper we give an improved algorithm whose competitive ratio is 1 log3.

📜 SIMILAR VOLUMES

A (log23 + 12) competitive algorithm for

A (log23 + 12) competitive algorithm for the counterfeit coin problem

✍ Peng-Jun Wan; Ding-Zhu Du 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 912 KB

Consider a set of coins where each coin is either of the heavy type or the light type. The problem is to identify the type of each coin with minimal number of weighings on a balanced scale. The case that only one coin, called a counterfeit, has a different weight from others, is a classic mathematic

A new competitive algorithm for the coun

A new competitive algorithm for the counterfeit coin problem

✍ X.D. Hu; P.D. Chen; F.K. Hwang 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 368 KB

A parallel algorithm for solving the 3D

A parallel algorithm for solving the 3D inverse scattering problem

✍ Ganquan Xie; Qisu Zou 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 306 KB

A parallel algorithm for solving the 3D inverse scattering problem is presented. The inverse problem considered is to determine a potential function from received wave data measured on a surface. The above inverse problem is transformed to a 3D nonlinear integral geometry equation. The principal ter

Balanced network flows. VIII. A revised

Balanced network flows. VIII. A revised theory of phase-ordered algorithms and the O( log(n2/m)/log n) bound for the nonbipartite cardinality matching problem

✍ Christian Fremuth-Paeger; Dieter Jungnickel 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 108 KB 👁 1 views

A New Approximation Algorithm for the St

A New Approximation Algorithm for the Steiner Tree Problem with Performance Ratio 5/3

✍ Hans Jürgen Prömel; Angelika Steger 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 100 KB

In this paper we present an RNC approximation algorithm for the Steiner tree problem in graphs with performance ratio 5r3 and RNC approximation algorithms for the Steiner tree problem in networks with performance ratio 5r3 q ⑀ for all ⑀ ) 0. This is achieved by considering a related problem, the min

Experimental evaluation of a partitionin

Experimental evaluation of a partitioning algorithm for the steiner tree problem in R2 and R3

✍ Sivakumar Ravada; Alan T. Sherman 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 614 KB

## Abstract We experimentally evaluate sequential and distributed implementations of an approximation partitioning algorithm by Kalpakis and Sherman for the __Geometric Steiner Minimum Tree Problem (GSMT)__ in __R^d^__ for __d__ = 2,3. Our implementations incorporate an improved method for combinin