The focus of attention problem

We consider the problem of assigning sensors to track targets so as to minimize the expected error in the resulting estimation for target locations. The so-called Focus of Attention problem deals with the special case where every target is tracked by one pair of range sensors.

We provide a complete complexity and approximability analysis of the Focus Of Attention problem: We establish its strong NP-hardness, and we construct a polynomial time approximation scheme for it.