作者：
Rao, NSVOak Ridge Natl Lab
Ctr Engn Syst Adv Res Div Math & Comp Sci Intelligent Syst Sect Oak Ridge TN 37831 USA
Due to the increasing role of quickest paths for on-demand routing in computer networks, it is important to compute them faster, perhaps, by trading-off the quality for computational speed. We consider the computation...
详细信息
Due to the increasing role of quickest paths for on-demand routing in computer networks, it is important to compute them faster, perhaps, by trading-off the quality for computational speed. We consider the computation of a quickest path from a source node to a destination node for a given message size in a network with n nodes and m links each of which is specified by bandwidth and delay. Every known quickest path algorithm computes m shortest paths either directly or indirectly, and this step contributes to most of its computational complexity which is generally of the form O(m(2) + mn log n). We present a probabilistic quickest path algorithm that computes an approximate quickest path with time complexity O(pm + pn log n) by randomly selecting p less than or equal to m bandwidths at which the shortest paths are computed. We show that the delay of the computed path is close to optimal with a high probability that approaches 1 exponentially fast with respect to p/m. Simulation results indicate that this algorithm computes the optimal quickest paths with p/m < 0.1 for almost all randomly generated networks with n > 40. We also present an algorithm to compute the path-table consisting of these approximate quickest paths with the same time complexity of 0(pm + pn log n). (C) 2003 Elsevier B.V. All rights reserved.
probabilistic algorithms to evaluate result reliability in qualitativechromatographic analysis are discussed in the paper. The elementary uncertainty (P0), concerned witha single test (comparison of sample and referen...
详细信息
probabilistic algorithms to evaluate result reliability in qualitativechromatographic analysis are discussed in the paper. The elementary uncertainty (P0), concerned witha single test (comparison of sample and reference peak positions), is treated as the sum ofmisidentification and omission probabilities. Both constituents are calculated separately using thesimplified model and Laplace functions. In the model, the main reasons for elementary uncertaintiesare random normally distributed deviations during retention characteristic measurement. algorithmsto calculate both constituents of P_0 have to take into account real measurement precision, supposedcomposition of the sample, content of the database, chosen coincidence criterion and other *** a high selectivity of retention, the 3σ value is recommended as the most convenient coincidencecriterion. It leads to more reliable and unambiguous attribution of peaks in the chromatogram. Forcases that are more complicated, the probabilistic algorithms based upon Bernoulli theorem areproposed to calculate the summary uncertainty of identification, concerned with the multiple *** take into account P_0 value, the number of repeated single tests (n) in the similar ordifferent conditions, and chosen identification criterion K (minimal number of coincidences). Theabove-mentioned algorithms lead to a priori optimisation of the mode of operation of anyidentification software system associated with the chromatograph. They can be useful during ametrological validation of corresponding qualitative analysis methods.
This dissertation concentrates on recent results on probabilistic robust controller design. In contrast to approaches taken in classical robustness theory, probabilistic robust controller design allows for a small ris...
详细信息
This dissertation concentrates on recent results on probabilistic robust controller design. In contrast to approaches taken in classical robustness theory, probabilistic robust controller design allows for a small risk of performance violation. This results, in many cases, in a significant reduction of the computational complexity of the controller design cycle and/or a significant reduction of the controller complexity even for a low level of risk of performance violation. In contrast to several of the probabilistic approaches in the control literature, we explore the problems' structure, i.e., convexity, to design more efficient algorithms. For a class of design problems which are convex in controller parameters, we introduce stochastic optimization methods to solve them. For a large class of non-convex problems, we provide a new approach which is shown to converge to the desired robust controller. This is accomplished by choosing an appropriate set of intermediate optimization variables at each iteration. Most of the results provided address the problem of designing robust output feedback controllers, where one directly determines the transfer function of the controller. Preliminary results are also presented on the design of robust static linear state feedback controllers.
Reachability routing is a newly emerging paradigm in networking, where the goal is to determine all paths between a sender and a receiver. It is becoming relevant with the changing dynamics of the Internet and the eme...
详细信息
Reachability routing is a newly emerging paradigm in networking, where the goal is to determine all paths between a sender and a receiver. It is becoming relevant with the changing dynamics of the Internet and the emergence of low-bandwidth wireless/ad hoc networks. This thesis presents the case for reinforcement learning (RL) as the framework of choice to realize reachability routing, within the confines of the current Internet backbone infrastructure. The setting of the reinforcement learning problem offers several advantages, including loop resolution, multi-path forwarding capability, cost-sensitive routing, and minimizing state overhead, while maintaining the incremental spirit of the current backbone routing algorithms. We present the design and implementation of a new reachability algorithm that uses a model-based approach to achieve cost-sensitive multi-path forwarding. Performance assessment of the algorithm in various troublesome topologies shows consistently superior performance over classical reinforcement learning algorithms. Evaluations of the algorithm based on different criteria on many types of randomly generated networks as well as realistic topologies are presented.
Proximity searches become very difficult on "high dimensional" metric spaces, that is, those whose histogram of distances has a large mean and/or a small variance. This so-called "curse of dimensionalit...
详细信息
Proximity searches become very difficult on "high dimensional" metric spaces, that is, those whose histogram of distances has a large mean and/or a small variance. This so-called "curse of dimensionality", well known in vector spaces, is also observed in metric spaces. The search complexity grows sharply with the dimension and with the search radius. We present a general probabilistic framework applicable to any search algorithm and whose net effect is to reduce the search radius. The higher the dimension, the more effective the technique. We illustrate empirically its practical performance on a particular class of algorithms, where large improvements in the search time are obtained at the cost of a very small error probability. (C) 2002 Elsevier Science B.V All rights reserved.
We solve two computational problems concerning plane algebraic curves over finite fields: generating a uniformly random point, and finding all points deterministically in amortized polynomial time (over a prime field,...
详细信息
We solve two computational problems concerning plane algebraic curves over finite fields: generating a uniformly random point, and finding all points deterministically in amortized polynomial time (over a prime field, for nonexceptional curves).
This paper studies the evaluation of routing algorithms from the perspective of reachability routing, where the goal is to determine all paths between a sender and a receiver. Reachability routing is becoming relevant...
详细信息
This paper studies the evaluation of routing algorithms from the perspective of reachability routing, where the goal is to determine all paths between a sender and a receiver. Reachability routing is becoming relevant with the changing dynamics of the Internet and the emergence of low-bandwidth wireless/ad hoc networks. We make the case for reinforcement learning as the framework of choice to realize reachability routing, within the confines of the current Internet infrastructure. The setting of the reinforcement learning problem offers several advantages, including loop resolution, multi-path forwarding capability, cost-sensitive routing, and minimizing state overhead, while maintaining the incremental spirit of current backbone routing algorithms. We identify research issues in reinforcement learning applied to the reachability routing problem to achieve a fluid and robust backbone routing framework. This paper also presents the design, implementation and evaluation of a new reachability routing algorithm that uses a model-based approach to achieve cost-sensitive multi-path forwarding;performance assessment of the algorithm in various troublesome topologies shows consistently superior performance over classical reinforcement learning algorithms. The paper is targeted toward practitioners seeking to implement a reachability routing algorithm. (C) 2003 Published by Elsevier B.V.
Centroidal Voronoi tessellations (CVTs) are Voronoi tessellations of a region such that the generating points of the tessellations are also the centroids of the corresponding Voronoi cells. In this paper, some probabi...
详细信息
Centroidal Voronoi tessellations (CVTs) are Voronoi tessellations of a region such that the generating points of the tessellations are also the centroids of the corresponding Voronoi cells. In this paper, some probabilistic methods for determining CVTs and their parallel implementations on distributed memory systems are presented. By using multi-sampling in a new probabilistic algorithm we introduce, more accurate and efficient approximations of CVTs are obtained without the need to explicit construct Voronoi diagrams. The new algorithm lends itself well to parallelization, i.e., near prefect linear speed up in the number of processors is achieved. The results of computational experiments performed on a CRAY T3E-600 system are provided which illustrate the superior sequential and parallel performance of the new algorithm when compared to existing algorithms. In particular, for the same amount of work, the new algorithms produce significantly more accurate CVTs. (C) 2002 Elsevier Science B.V. All rights reserved.
We present a novel multi-resolution point sample rendering algorithm for keyframe animations. The algorithm accepts triangle meshes of arbitrary topology as input which are animated by specifying different sets of ver...
详细信息
We present a novel multi-resolution point sample rendering algorithm for keyframe animations. The algorithm accepts triangle meshes of arbitrary topology as input which are animated by specifying different sets of vertices at keyframe positions. A multi-resolution representation consisting of prefiltered point samples and triangles is built to represent the animated mesh at different levels of detail. We introduce a novel sampling and stratification algorithm to efficiently generate suitable point sample sets,for moving triangle meshes. Experimental results demonstrate that the new data structure can be used to render highly complex keyframe animations like crowd scenes in real-time.
We develop probabilistic algorithms that solve problems of geometric elimination theory using small memory resources. These algorithms are obtained by means of the adaptation of a general transformation due to A. Boro...
详细信息
We develop probabilistic algorithms that solve problems of geometric elimination theory using small memory resources. These algorithms are obtained by means of the adaptation of a general transformation due to A. Borodin which converts uniform boolean circuit depth into sequential (Turing machine) space. The boolean circuits themselves are developed using techniques based on the computation of a primitive element of a suitable zero-dimensional algebra and diophantine considerations. Our algorithms improve considerably the space requirements of the elimination algorithms based on rewriting techniques (Grobner solving), having simultaneously a time performance of the same kind of them.
暂无评论