Multiple-Interval Coverage for Resource Management of Passive Surveillance Systems

Abstract Passive surveillance systems (PSS) are used to detect and track various targets by processing the electromagnetic signals they release. The study and design of the resource management algorithm for these systems revealed several phenomena and combinatorial problems with crucial theoretical properties. In this article, we first prove the completeness of the algorithm used to generate receiver settings that determine which frequency bands the PSS monitors. Next, we formulate a new optimization problem called multiple-interval coverage (MIC), which is used to determine how often each of the generated settings must be used by the PSS. We show that the MIC problem is closely related to the multicover problem, which is an extension of the well-known set cover problem. The uniqueness of MIC stems from the fact that both covered elements and covers are multiple-intervals. We propose a notation to distinguish between different variants of the problem and prove that some of them can be solved in polynomial time. Finally, we prove that the MIC problem is NP-hard even when restricted to 2-interval covers.