Combinatorial Pair Testing: Distinguishing Workers from Slackers

Abstract

We formalize a problem we call combinatorial pair testing (CPT), which has applications to the identification of uncooperative or unproductive participants in pair programming, massively distributed computing, and crowdsourcing environments. We give efficient adaptive and nonadaptive CPT algorithms and we show that our methods use an optimal number of testing rounds to within constant factors. We also provide an empirical evaluation of some of our methods.

12 pages. Extended version of a paper to appear at the Algorithms and Data Structures Symposium (WADS 2013)

References in corpus (1)

• Pipelined Algorithms to Detect Cheating in Long-Term Grid Computations

Cited by in corpus (2)

• Smart elements in combinatorial group testing problems
• Conscious and controlling elements in combinatorial group testing problems with more defectives