arXiv preprint ·
Backtracking Candidate Elimination: A One-Pass Algorithm for the Chip Testing Problem
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
In the chip testing problem, we are given $n$ chips, strictly more than half of which are good. Chips can test one another in pairs; a good chip always reports the status of the other chip correctly, whereas a bad chip may report arbitrarily and adversarially. The goal is to identify a single chip that is guaranteed to be good. The problem originates in system-level fault diagnosis and is closely related to the "knights and spies" puzzle. The standard textbook solution is a halving recursion that tests disjoint pairs in rounds and keeps one chip from each consistent pair. We present the Backtracking Candidate Elimination (BCE) algorithm, a sequential alternative that scans the chips once while maintaining a current candidate and a stack of retained chips. Every chip is tested at most once as the incoming chip; when a test is inconclusive the candidate and the incoming chip are discarded together, and the algorithm backtracks to the most recently retained chip. BCE uses at most $n-1$ tests and $O(n)$ time, needs no parity case analysis, and works online. Its correctness follows from two invariants: the retained chips all have the same type, and every discarded pair contains at least one bad chip. We explain how BCE can be viewed as the Boyer-Moore majority vote algorithm with its counter replaced by a stack of physical witnesses, and why that replacement is needed. We also give an early termination rule and a variant for the weaker model of one-directional tests.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Factorisability of Low Dimensional Non-Negative Integer Matrices
Vertex-Coloring Edge-Weighting: Kernelization and Generalization
Inverse knapsack at two capacities: which pairs of value-cardinality hulls are realizable?
Minimum Sum Vertex Cover via Minimum Vertex Cover
Transposition achieves OPT$+O(1)$ in polynomial time for IID list update
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.