Paper Info
Title
Finding Defectives On A Line By Random Docking And Interval Group Tests
Abstract
Suppose that some of the n elements of a totally ordered structure is defective, and several repair robots are at our disposal. They can dock at a random element, move at unit speed or leave, and send each other signals if there is no defective between them. We show that, by using only two robots that obey simple rules, the defective can be localized in O(root n) time, which is also optimal. A variation of our strategy needs three robots but has a more predictable behavior. The model is motivated by a conjectured DNA repair mechanism, and it combines group testing with geometric search.
Year
DOI
Venue
2017
10.1142/S179383091750029X
DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS
Keywords
Field
DocType
Cooperative robots, interval group testing, cow path problem
DOCK,Random element,Combinatorics,Docking (dog),Group tests,Algorithm,Robot,Group testing,Mathematics,Predictable behaviour
Journal
Volume
Issue
ISSN
9
3
1793-8309
Citations 
PageRank 
References 
0
0.34
2
Authors
1
Name
Order
Citations
PageRank
Peter Damaschke147156.99