Browsing by Author "Cheng, Xiuzhen"
Now showing 1 - 6 of 6
Results Per Page
Sort Options
Item A Polynomial Time Approximation Scheme for the problem of Interconnecting Highways(2000-11-28) Cheng, Xiuzhen; Kim, Joon-Mo; Lu, BingThe objective of the Interconnecting Highways problem is to construct roads of minimum total length to interconnect given highways under the constraint that the roads can intersect each highway only at one point in a designated interval which is a line segment. We present a polynomial time approximation scheme for this problem by applying Arora's framework in [2]. For every fixed c>1 and given any n line segments in the plane, a randomized version of the scheme finds a (1+1/c)-approximation to the optimal cost in O(n o(c)log n) time.Item A Quadratic Integer Programming with Application in Chaotic Mappings of Complete Multipartite Graphs(2000-10-02) Fu, Hung-Lin; Shiue, Chin-lin; Cheng, Xiuzhen; Du, Ding-Zhu; Kim, Joon-MoLet alpha be a permutation of V(G) of a connected graph G. Define the total relative displacement of alpha in G by where dG(x,y) is the length of the shortest path between x and y in G. Let pi*(G) be the maximum value of deltaalpha(G) among all permutations of V(G) and the permutation which realizes pi*(G) is called a chaotic mapping of G. In this paper, we study the chaotic mappings of complete multipartite graphs. The problem will reduce to a quadratic integer programming. We characterize its optimal solution and present an algorithm running in O(n5log n) time where n is the total number of vertices in a complete multipartite graph.Item Polynomial-Time Approximation Scheme for Minimum Connected Dominating Set in Ad Hoc Wireless Networks(2002-01-22) Cheng, Xiuzhen; Huang, Xiao; Li, Deying; Du, Ding-ZhuA connected dominating set in a graph is a subset of vertices such that every vertex is either in the subset or adjacent to a vertex in the subset and the subgraph induced by the subset is connected. The minimum connected dominating set is such a vertex subset with minimum cardinality. An application in ad hoc wireless networks requires the study of the minimum connected dominating set in unit-disk graphs. In this paper, we design $(1+1/s)$-approximation for the minimum connected dominating set in unit-disk graphs, running in time $n^{O((slog s)^2)}$.Item Relay Sensor Placement in Wireless Sensor Networks(2002-01-22) Cheng, Xiuzhen; Du, Ding-Zhu; Wang, Lusheng; Xu, BaogangIn this paper, we propose a novel idea of maintaining connectivity by introducing relay sensors in a wireless sensor network. We restrict our consideration to a very important class of wireless sensor networks such as biomedical sensor networks, in which the locations of the sensors are fixed and the placement can be pre-determined. We formulate our problem to the NP-hard network optimization problem named Steiner Minimum Tree with Minimum number of Steiner Points (SMT-MSP) and present two approximate solutions. Meanwhile, we study the topology improvement in a wireless sensor network when relay sensors are introduced. In other words, we restrict transmission power of each sensor to a small value and use relay sensors to guarantee connectivity. The performance parameters under consideration are $P$, the total per node minimum power needed to maintain connectivity, and $D$, the maximum degree in the minimum power topology (maintained by $P$).Simulation study shows that with the introduction of relay sensors, we achieve better performance, especially for sparse topology.Item Statistical Comparisons of Multiple Classifiers(2001-06-15) Cheng, Xiuzhen; Chen, DechangThis paper discusses the issue of comparing multiple classifiers, applied to the same test dataset of a classification problem. Assume that the output is 0 if a classifier correctly classifies a test feature point and the output is 1 otherwise.Then all the outputs from a given classifier constitute a sample of 0 and 1, and all the samples are correlated. From these dependent samples, we use Cochran's Q statistic, as an overall test statistic, to detect whether or not the error rates of the classifiersare significantly different. When the null hypothesis that the error rates are equal is rejected, a thorough analysis of the nature of the error rates, such as the ranking of the error rates, is undertaken. For this purpose, we employ the Scheffe and Bonferroni multiple comparison procedures, based on dependent samples. We also use examples to demonstrate how to make these statistical comparisons.Item Virtual Backbone-Based Routing in Multihop Ad Hoc Wireless Networks(2002-01-22) Cheng, Xiuzhen; Du, Ding-ZhuRecent research shows that the flooding mechanism (for topology update or route request) used in existing protocols for ad hoc wireless networks greatly degrades the network capacity. If we force the effective broadcasts of control packets happen in a small subset of hosts in thenetwork, the protocol overhead caused by global flooding can be substantially reduced. This is the basic idea of virtual backbone-based routing in ad hoc wireless networks, in which all hosts forming the virtual backbone are in charge of control packets dissemination. This strategy works quite effectively in decreasing message overhead. However, constructing a virtual backbone is not trivial. In our study, the virtual backbone is approximated by minimum connected dominating set (MCDS) in unit-disk graphs, which is NP-hard. We propose two distributed time/message efficient approximation algorithms to compute MCDS. Both algorithms have linear message complexities. Algorithm I is cost-aware, which accommodates the strict network resources in virtual backbone construction. Algorithm II is degree-aware, which generates the best result in literature so far to our knowledge. We not only give theoretical performance analysis for both algorithms, but also conduct extensive simulation to compare our algorithms with those in literature. Simulation results and theoretical analysis showthat both algorithms perform very well.