Computational complexity of distributed detection problems with information constraints |
| |
Authors: | NSV Rao SS Iyengar RL Kashyap |
| |
Affiliation: | Department of Computer Science, Old Dominion University, Norfolk, VA 23529-0162, U.S.A. Department of Computer Science, Louisiana State University, Baton Rouge, LA 70803, U.S.A. Department of Electrical Engineering, Purdue University, West Lafayette, IN 47907, U.S.A. |
| |
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. |
| |
Keywords: | Distributed detection networks algorithms and complexity computational intractability |
本文献已被 ScienceDirect 等数据库收录! |
|