We present DRR-gossip, an energy-efficient and robust aggregate computation algorithm in wireless sensor networks. We prove that the DRR-gossip algorithm requires O(n) messages and O(n(3/2)/log(1/2)n) one-hop wireless...
详细信息
ISBN:
(纸本)9781605583969
We present DRR-gossip, an energy-efficient and robust aggregate computation algorithm in wireless sensor networks. We prove that the DRR-gossip algorithm requires O(n) messages and O(n(3/2)/log(1/2)n) one-hop wireless transmissions to obtain aggregates on a random geometric graph. This reduces the energy consumption by at least a factor of 1/log(n) over the standard uniform gossip algorithm. Experiments validate the theoretical results and show that DRR-gossip needs much less transmissions than other gossip-based schemes.
Boltzmann models from statistical physics, combined with methods from analytic combinatorics, give rise to efficient algorithms for the random generation of combinatorials objects. This paper proposes a Boltzmann samp...
详细信息
In a paper that considered arithmetic precision as a limited resource in the design and analysis of algorithms, Liotta, Preparata and Tamassia defined an "implicit Voronoi diagram" supporting logarithmic-tim...
详细信息
ISBN:
(纸本)9783642033667
In a paper that considered arithmetic precision as a limited resource in the design and analysis of algorithms, Liotta, Preparata and Tamassia defined an "implicit Voronoi diagram" supporting logarithmic-time proximity queries using predicates of twice the precision of the input and query coordinates. They reported, however, that computing this diagram uses five times the input precision. We define a reduced-precision Voronoi diagram that similarly supports proximity queries, and describe a randomized incremental construction using only three times the input precision. The expected construction time is O(n(log n + log mu)), where mu is the length of the longest Voronoi edge;we can construct the implicit Voronoi from the reduced-precision Voronoi in linear time.
The hardware and architecture approach to randomized algorithms is defined not only by the evaluation of systems that paved the way for the emulation of digital-to-analog converters, but also by the essential need for...
详细信息
The hardware and architecture approach to randomized algorithms is defined not only by the evaluation of systems that paved the way for the emulation of digital-to-analog converters, but also by the essential need for expert systems. After years of important research into IPv7, we show the understanding of the Turing machine. Our focus here is not on whether the infamous psychoacoustic algorithm for the important unification of SCSI disks and systems by M. Bharadwaj et al. runs in O(n) time, but rather on proposing an analysis of linked lists.
This paper studies Monte Carlo methods and other stochastic algorithms from the super-recursive algorithmic perspective. Advantages of such super-recursive algorithms as inductive and limit Turing machines are demonst...
详细信息
This paper studies Monte Carlo methods and other stochastic algorithms from the super-recursive algorithmic perspective. Advantages of such super-recursive algorithms as inductive and limit Turing machines are demonstrated.
We present a distributed algorithm that constructs an O(log n)-approximate minimum spanning tree (MST) in any arbitrary network. This algorithm runs in time (O) over tilde (D(G)+L(G, w)) where L(G, w) is a parameter c...
详细信息
We present a distributed algorithm that constructs an O(log n)-approximate minimum spanning tree (MST) in any arbitrary network. This algorithm runs in time (O) over tilde (D(G)+L(G, w)) where L(G, w) is a parameter called the local shortest path diameter and D(G) is the (unweighted) diameter of the graph. Our algorithm is existentially optimal (up to polylogarithmic factors), i.e., there exist graphs which need Omega(D(G) + L(G, w)) time to compute an H-approximation to the MST for any H is an element of [1, Theta(log n)]. Our result also shows that there can be a significant time gap between exact and approximate MST computation: there exists graphs in which the running time of our approximation algorithm is exponentially faster than the time-optimal distributed algorithm that computes the MST. Finally, we show that our algorithm can be used to find an approximate MST in wireless networks and in random weighted networks in almost optimal (O) over tilde (D(G)) time.
We investigate the existence and efficient algorithmic construction of close to optimal independent sets in random models of intersection graphs. In particular, (a) we propose a new model for random intersection graph...
详细信息
We investigate the existence and efficient algorithmic construction of close to optimal independent sets in random models of intersection graphs. In particular, (a) we propose a new model for random intersection graphs (G(n),(m),((p) over right arrow)) which includes the model of [M. Karonski, E.R. Scheinerman, K.B. Singer-Cohen, On random intersection graphs: The subgraph problem, Combinatorics, Probability and Computing journal 8 (1999), 131-159] (the "uniform" random intersection graph models) as an important special case. We also define an interesting variation of the model of random intersection graphs, similar in spirit to random regular graphs. (b) For this model we derive exact formulae for the mean and variance of the number of independent sets of size k (for any k) in the graph. (c) We then propose and analyse three algorithms for the efficient construction of large independent sets in this model. The first two are variations of the greedy technique while the third is a totally new algorithm. Our algorithms are analysed for the special case of uniform random intersection graphs. Our analyses show that these algorithms succeed in finding close to optimal independent sets for an interesting range of graph parameters. (c) 2008 Elsevier B.V. All rights reserved.
In this paper, we introduce a new randomized, partition-based algorithm for the problem of computing the number of inversion pairs in an unsorted array of n numbers. The algorithm runs in expected time O(n . log n) an...
详细信息
In this paper, we introduce a new randomized, partition-based algorithm for the problem of computing the number of inversion pairs in an unsorted array of n numbers. The algorithm runs in expected time O(n . log n) and uses O(n) extra space. The expected time analysis of the new algorithm is different from the analyses existing in the literature, in that it explicitly uses inversion pairs. The problem of determining the inversion pair cardinality of an array finds applications in a number of design domains, including but not limited to real-time scheduling and operations research. At the heart of our algorithm is a new inversion pair conserving partition procedure that is different from existing partition procedures such as Hoare-partition and Lomuto-partition. Although the algorithm is not fully adaptive, we believe that it is the first step towards the design of an adaptive, partition-based sorting algorithm whose running time is proportional to the number of inversion pairs in the input.
This paper considers uncertain constrained systems, and develops two algorithms for computing a probabilistic output admissible (POA) set which is a set of initial states probabilistically assured to satisfy the const...
详细信息
This paper considers uncertain constrained systems, and develops two algorithms for computing a probabilistic output admissible (POA) set which is a set of initial states probabilistically assured to satisfy the constraint. The first algorithm is inspired by an existing randomized sequential technique. The second algorithm alleviates the computational effort based on heuristics. The present algorithms terminate in a finite number of iterations and provide a POA set. Additionally, we can obtain information on the size of the resulting set a posteriori. A numerical simulation demonstrates the applicability of the POA set to a control system design scheme. (C) 2007 Elsevier Ltd. All rights reserved.
This paper introduces performance at risk and conditional performance at risk as design metrics for the formulation of robust control design. These two metrics are used to characterize the high percentile or tail dist...
详细信息
This paper introduces performance at risk and conditional performance at risk as design metrics for the formulation of robust control design. These two metrics are used to characterize the high percentile or tail distribution of a performance specification when system uncertain parameters are random variables described by statistical distributions. The probabilistic robust control design is then formulated as a minimization problem with respect to the (conditional) performance at risk or as a constrained problem in terms of them. Performance specifications in terms of the high percentile or tail distribution are more stringent than that are defined in terms of the average (mean) value, which are often used in current literature for probabilistic robust control. Furthermore, the convexity of the conditional performance at risk does not have particular requirements on the underlying distribution of uncertain parameters;thus, convex optimization can be applied to the probabilistic robust control with respect to uncertain parameters with general distributions. The proposed probabilistic robust approach is applied to search solutions to linear matrix inequality containing random parametric uncertainties as well as to design a stabilizing controller for polynomial vector fields subject to random parametric uncertainties. Copyright (C) 2007 John Wiley & Sons, Ltd.
暂无评论