Abstract
For a system consisting of a set of sensors S = {S1, S2, ..., Sm} and a set of objects O = {O1, O2, ..., On}, there are information constraints given by a relation R ⊆ S × O such that (Si, Oj) ∈ R if and only if Si is capable of detecting Oj. Each (Si, Oj) ∈ R is assigned a confidence factor (a positive real number) which is either explicitly given or can be efficiently computed. Given that a subset of sensors have detected obstacles, the detection problem is to identify a subset H ⊆ O with the maximum confidence value. The computational complexity of the detection problem, which depends on the nature of the confidence factor and the information constraints, is the main focus of this paper. This problem exhibits a myriad of complexity levels ranging from a worst-case exponential (in n) lower bound in a general case to an O(m + n) time solvability. We show that the following simple versions of a detection problem are computationally intractable: (a) deterministic formulation, where confidence factors are either 0 or 1; (b) uniform formulation where (Si, Oj) ∈ R, for all Si ∈ S, Oj ∈ O; (c) decomposable systems under multiplication operation. We then show that the following versions are solvable in polynomial (in n) time: (a) single object detection; (b) probabilistically independent detection; (c) decomposable systems under additive and nonfractional multiplicative measures; and (d) matroid systems.
Original language | English |
---|---|
Pages (from-to) | 445-451 |
Number of pages | 7 |
Journal | Computers and Electrical Engineering |
Volume | 19 |
Issue number | 6 |
DOIs | |
State | Published - Nov 1993 |
Externally published | Yes |
Funding
tA preliminary version of this paper has been presented at the Fourth ISMM International Conference on Parallel and Distributed Computing and Systems, Washington, DC, 8-11 October (1991). §Partially funded by an LEQSF grant from Louisiana State University Board of Regents. ~:Partially funded by National Science Foundation under Grant No. IRI-9108610, Virginia's Center for Innovative Technology under Grant No. INF-90-015 and Old Dominion University Summer Faculty Research Fellowship for 1991.
Keywords
- Distributed detection networks
- algorithms and complexity
- computational intractability