Hostname: page-component-74656f9884-rngvg Total loading time: 0 Render date: 2026-11-06T11:01:40.160Z Has data issue: false hasContentIssue false

Improved Results for Competitive Group Testing

Published online by Cambridge University Press:  15 February 2005

JENS SCHLAGHOFF
Affiliation:
RWTH Aachen, Lehrstuhl II für Mathematik, D-52062 Aachen, Templergraben 55, Germany (e-mail: triesch@math2.rwth-aachen.de)
EBERHARD TRIESCH
Affiliation:
RWTH Aachen, Lehrstuhl II für Mathematik, D-52062 Aachen, Templergraben 55, Germany (e-mail: triesch@math2.rwth-aachen.de)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We consider algorithms for group testing problems when nothing is known in advance about the number of defectives. Du and Hwang suggested measuring the quality of such algorithms by its so-called (first) competitive ratio (see the Introduction). Later, Du and Park suggested a second kind of competitive ratio. For each kind of competitiveness, we improve the best-known bounds: in the first case, from 1.65 to $1.5+\ep$, and in the second from 16 to 4.

Information

Type
Paper
Copyright
© 2005 Cambridge University Press