China
Africa
Explore chapters and articles related to this topic
Sensor Networking Software and Architectures
Published in John R. Vacca, Handbook of Sensor Networking, 2015
Xiang et al. [57,58] studied the joint optimization between packet packing and the latency of data delivery. They provide a comprehensive computational complexity analysis on this scheduling problem in sensor networks. The authors proved the strong NP-hardness of this problem via a reduction from SAT problem. They also show that certain special packing constraints make this problem polynomial solvable. Based on the complexity analysis, the authors designed a distributed, online protocol named tPack to make packing decisions to maximize the local utility of packet packing at each node. Experiment results on the NetEye test bed show that tPack is able to provide at least a reduction of 70% transmission cost in various heavy traffic patterns in a 120 -node dense topology.
An integer linear programing approach to find trend-robust run orders of experimental designs
Published in Journal of Quality Technology, 2019
Our solution approach is based on the 1-norm minimization. To show that this problem is non-deterministic polynomial-time hard, or NP hard, we show how another NP-hard problem naturally reduces to the 1-norm minimization. NP hardness is a property introduced by Cook (1971) that defines a class of problems characterized by their intractability. Consider an arbitrary design with model matrix X and a set of covariates contained in the matrix Z. It is straightforward to see that the partition problem (see Garey and Johnson 1979, 223) reduces to our integer optimization problem. Given a set of integers, the partition problem looks for two subsets such that the sum of the elements in each subset is equal. This problem is known to be NP hard, also when those subsets are of equal size. To see the reduction, consider a matrix X that has only one column containing an equal number of +1’s and –1’s. We include the elements of the partition set in the column vector Z. Then, if equals zero, we have found a solution to the partition problem. Therefore, in general, our mixed integer problem is NP hard, so our optimization algorithm based on integer programing techniques is justified.