Hostname: page-component-78c5997874-mlc7c Total loading time: 0 Render date: 2024-11-06T14:06:58.152Z Has data issue: false hasContentIssue false
  • English
  • Français

Improved Results for Competitive Group Testing

Published online by Cambridge University Press:  15 February 2005

JENS SCHLAGHOFF  and
EBERHARD TRIESCH
JENS SCHLAGHOFF
Affiliation:
RWTH Aachen, Lehrstuhl II für Mathematik, D-52062 Aachen, Templergraben 55, Germany (e-mail: [email protected])
EBERHARD TRIESCH
Affiliation:
RWTH Aachen, Lehrstuhl II für Mathematik, D-52062 Aachen, Templergraben 55, Germany (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 14 , Issue 1-2 , January 2005 , pp. 191 - 202
Copyright
© 2005 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)