In the first work, our major contribution is to develop the best approximation algorithm that one can achieve for our problem. That is, our algorithm always achieves a factor of the optimal performance, i.e., the maximum detection coverage, and the approximation ratio is the best achievable for our problem among all polynomial-time algorithms. Our algorithm is based on LP rounding technique, where we first formulate the problem as an integer linear program, then relax the integer constraints and solve the resulting linear program (LP) relaxation, which takes polynomial time, and finally round the optimal LP solution, which contains fractional values in general, to an integer value, either 0 or 1. We present two rounding schemes—randomized and deterministic. The probabilistic rounding scheme achieves the best approximation ratio probabilistically (i.e., on average) while the deterministic rounding scheme attains it deterministically (i.e., each time it runs).

In the second work, our main contribution in this work is to develop a distributed algorithm that preserves the same approximation ratio as our prior (centralized) algorithm while providing a distributed solution that is amenable to online implementation. Further, our algorithm is cost-effective in terms of communication and computational overheads. Also, we present two operational modes of our algorithm for two types of networks that have different rates of network changes—a proactive mode for fast varying networks and a reactive mode for slowly varying networks. The design milestone of our distributed algorithm is the proximal optimization algorithm and the duality theory. They enable us to decompose the given global optimization problem into sub-problems that can be solved in a distributed manner requiring only local communication among neighboring nodes.

In the third work, which is on going, our goal is to minimize the number of monitoring nodes being activated while meeting a given detection accuracy level for all ad hoc nodes by judiciously selecting a set of monitoring nodes to be activated and assigning channels to the selected monitoring nodes. We show that finding any feasible solution to the problem is NP-hard. That is, it is NP-hard to even find any solution that activates all monitoring nodes and gives a channel assignment that meets the desired accuracy level of the network diagnoses. Alternatively, we consider a problem where we find a channel assignment that maximizes the detection coverage, in terms of the number of ad hoc nodes, subject to meeting the desired detection accuracy. We are developing algorithms to solve this alternative problem.