97-82: Diagnosing Double Regular Systems

DIMACS TR: 97-82

Diagnosing Double Regular Systems

Authors: Endre Boros, Tonguc Unluyurt

ABSTRACT
We consider the problem of testing sequentially the components of a double regular system, when the testing of each component is costly. Generalizing earlier results about $k$-out-of-$n$ systems, we provide a polynomial time algorithm for the most cost-effficient sequential testing of double regular systems. The algorithm can be implemented to work efficiently both for explicitly given systems, and for systems given by an oracle.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-82.ps.gz

DIMACS Home Page