Du, Dingzhu
Permanent URI for this collectionhttps://hdl.handle.net/10735.1/4209
Dr. Dingzhu Du serves as a professor in the Department of Computer Science. He is also a co-director of the Data Communication and Data Management Laboratory. His research interests and areas of expertise inclue:
- Combinatorial optimization
- Communication networks
- Theory of computation
Browse
Recent Submissions
Item Quality of Barrier Cover with Wireless Sensors(Inderscience Enterprises Ltd, 2019-04-01) Wu, Weili; Zhang, Zhao; Gao, Chuangen; Du, Hai; Wang, Hua; Du, Dingzhu; Wu, Weili; Du, DingzhuA set of wireless sensors is called a barrier cover if they can monitor the boundary of an area so that an intruder cannot enter the area without being found by any sensor. The quality of a barrier cover is the shortest length of path along which an intruder can enter the area from outside. We study four problems, in this paper, related to the quality of the barrier cover and give their computational complexity and algorithmic solutions.Item Set Function Optimization(Operations Research Society of China, 2018-12-17) Wu, Weili; Zhang, Z.; Du, Dingzhu; Wu, Weili; Du, DingzhuThis article is an introduction to recent development of optimization theory on set functions, the nonsubmodular optimization, which contains two interesting results, DS (difference of submodular) functions decomposition and sandwich theorem, together with iterated sandwich method and data-dependent approximation. Some potential research problems will be mentioned. © 2018, The Author(s).Item Maximisation of the Number of β-View Covered Targets in Visual Sensor Networks(Inderscience Enterprises Ltd., 2019-03-24) Guo, L.; Li, D.; Wang, Y.; Zhang, Z.; Tong, Guangmo; Wu, Weili; Du, Dingzhu; 56851698 (Wu, W); 288884264 (Du, D); Tong, Guangmo; Wu, Weili; Du, DingzhuIn some applications using visual sensor networks (VSNs), the facing directions of targets are bounded. Therefore existing full-view coverage (all the facing directions of a target constitutes a disk) is not necessary. We propose a novel model called β-view coverage model through which only necessary facing directions of a target are effectively viewed. This model uses much fewer cameras than those used by full-view coverage model. Based on β-view coverage model, a new problem called β-view covered target maximisation (BVCTM) problem is proposed to maximise the number of β-view covered targets given some fixed and freely rotatable camera sensors. We prove its NP-hardness and transform it into an Integer Linear Programming problem equivalently. Besides, a (1 - e - 1 )-factor approximate algorithm and a camera-utility based greedy algorithm are given for this problem. Finally, we conduct many experiments and investigate the influence of many parameters on these two algorithms. © 2019 Inderscience Enterprises Ltd.Item Breach-Free Sleep-Wakeup Scheduling for Barrier Coverage with Heterogeneous Wireless Sensors(Institute of Electrical and Electronics Engineers Inc.) Zhang, Z.; Wu, Weili; Yuan, Jing; Du, Dingzhu; 288884264 (Du, D); Wu, Weili; Yuan, Jing; Du, DingzhuBarrier Coverage plays a vital role in wireless sensor networks. Research on barrier coverage has mainly focused on the lifetime maximization and the critical conditions to achieve k-Barrier Coverage under various sensing models. When sensors are randomly deployed along the boundary of an area of interest, they may form several disjoint barrier covers. To maximize the lifetime of barrier coverage, those barrier covers need to be scheduled to avoid a security problem, call breach. In a heterogeneous wireless sensor network, given a set of barrier-covers each with a lifetime, we study the problem of finding a lifetime-maximizing subset with a breach-free sleep-wakeup scheduling. We first prove that it can be judged in polynomial time whether a given sleep-wakeup schedule is breach-free or not, but given a set of barrier-covers, it is NP-Complete to determine whether there exists a breach-free schedule. Then, we show that the problem of finding a lifetime-maximizing breach-free schedule is equivalent to the maximum node weighted path problem in a directed graph, and design a parameterized algorithm. Experimental results show that our algorithm significantly outperforms the heuristics proposed in the literature.Item A Zig-Zag Approach for Competitive Group TestingCheng, Yongxi; Du, Dingzhu; Xu, Yinfeng; 0000 0001 0891 4462 (Du, D); 88207689 (Du, D); 288884264 (Du, D)In many fault-detection problems, we want to identify defective items from a set of n items using the minimum number of tests. Group testing is a scenario in which each test is on a subset of items and determines whether the subset contains at least one defective item. In practice, the number d of defective items is often unknown in advance. In this paper, we present a new algorithm for the above group testing problem and prove that it has very good performance guarantee. More specifically, the number of tests used by the new algorithm is bounded from above by d log(n/d) + 3d + O(log² d). The new algorithm is designed based on a zig-zag approach that has not been studied before and is intuitive and easy to implement. When 0 < d < ρ₀ where ρ₀ = 1 − 4/e² = 0.45..., which holds for most practical applications, our new algorithm has better performance guarantee than any previous best result. Computational results show that the new algorithm has very good practical performances.