Computational complexity of distributed detection problems with information constraints

N. S.V. Rao, S. S. Iyengar, R. L. Kashyap

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

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 languageEnglish
Pages (from-to)445-451
Number of pages7
JournalComputers and Electrical Engineering
Volume19
Issue number6
DOIs
StatePublished - Nov 1993
Externally publishedYes

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

Fingerprint

Dive into the research topics of 'Computational complexity of distributed detection problems with information constraints'. Together they form a unique fingerprint.

Cite this