检索结果-内蒙古大学图书馆

Quasirandom rumor spreading: An experimental analysis

ACM Journal of Experimental Algorithmics 2008年第PP3.1–3.13期16卷 3.1–3.13页

作者： Benjamin Doerr Tobias Friedrich Marvin Künnemann Thomas Sauerwald Max-Planck-Institut für Informatik Germany Universität des Saarlandes Germany

We empirically analyze two versions of the well-known “randomized rumor spreading” protocol to disseminate a piece of information in networks. In the classical model, in each round, each informed node informs a random neighbor. In the recently proposed quasirandom variant, each node has a (cyclic) list of its neighbors. Once informed, it starts at a random position of the list, but from then on informs its neighbors in the order of the *** for sparse random graphs a better performance of the quasirandom model could be proven, all other results show that, independent of the structure of the lists, the same asymptotic performance guarantees hold as for the classical *** this work, we compare the two models experimentally. Not only does this show that the quasirandom model generally is faster, but it also shows that the runtime is more concentrated around the mean. This is surprising given that much fewer random bits are used in the quasirandom *** advantages are also observed in a lossy communication model, where each transmission does not reach its target with a certain probability, and in an asynchronous model, where nodes send at random times drawn from an exponential distribution. We also show that typically the particular structure of the lists has little influence on the efficiency.

关键词： Rumor spreading experimental analysis randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Fast computation of Fourier integral operators

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2007年第6期29卷 2464-2493页

作者： Candes, Emmanuel Demanet, Laurent Ying, Lexing Stanford Univ Dept Math Stanford CA 94305 USA Univ Texas Dept Math Austin TX 78712 USA

We introduce a general purpose algorithm for rapidly computing certain types of oscillatory integrals which frequently arise in problems connected to wave propagation, general hyperbolic equations, and curvilinear tomography. The problem is to numerically evaluate a so-called Fourier integral operator (FIO) of the form integral e(2 pi i Phi(x,xi))a(x,xi) (f) over cap(xi)d xi. at points given on a Cartesian grid. Here, xi is a frequency variable, (f) over cap(xi) is the Fourier transform of the input f, a(x,xi) is an amplitude, and Phi(x,xi) is a phase function, which is typically as large as |xi|;hence the integral is highly oscillatory. Because a FIO is a dense matrix, a naive matrix vector product with an input given on a Cartesian grid of size N by N would require O(N-4)operations. This paper develops a new numerical algorithm which requires O(N-2.5 log N) operations and as low as O(root N) in storage space (the constants in front of these estimates are small). It operates by localizing the integral over polar wedges with small angular aperture in the frequency plane. On each wedge, the algorithm factorizes the kernel e(2 pi i Phi(x,xi))a(x,xi) into two components: (1) a diffeomorphism which is handled by means of a nonuniform FFT and (2) a residual factor which is handled by numerical separation of the spatial and frequency variables. The key to the complexity and accuracy estimates is the fact that the separation rank of the residual kernel is provably independent of the problem size. Several numerical examples demonstrate the numerical accuracy and low computational complexity of the proposed methodology. We also discuss the potential of our ideas for various applications such as reflection seismology.

关键词： fourier integral operators generalized Radon transform separated representation nonuniform fast Fourier transform matrix approximation operator compression randomized algorithms reflection seismology

来源：评论

学校读者我要写书评

暂无评论

On the complete instability of interval polynomials

引用

SYSTEMS & CONTROL LETTERS 2007年第6期56卷 431-438页

作者： Dabbene, F. Polyak, B. T. Tempo, R. Politecn Torino CNR IEIIT I-10129 Turin Italy Russian Acad Sci Inst Control Sci Moscow 117997 Russia

In this paper, we study "complete instability" of interval polynomials, which is the counterpart of classical robust stability. That is, the objective is to check if all polynomials in the family are unstable. If not, a subsequent goal is to find a stable polynomial. To this end, we first propose a randomized algorithm which is based on a (recursive) necessary condition for Hurwitz stability. The second contribution of this paper is to provide a probability-one estimate of the volume of stable polynomials. These results are based on a combination of deterministic and randomized methods. Finally, we present two numerical examples and simulations showing the efficiency of the proposed methodology for small and medium-size problems. (c) 2006 Elsevier B.V. All rights reserved.

关键词： robust stability randomized algorithms interval polynomials

来源：评论

学校读者我要写书评

暂无评论

Polynomial-time algorithms for probabilistic solutions of parameter-dependent linear matrix inequalities

引用

AUTOMATICA 2007年第3期43卷 538-545页

作者： Oishi, Yasuaki Univ Tokyo Grad Sch Informat Sci & Technol Dept Math Informat Bunkyo Ku Tokyo 1138656 Japan

A randomized approach is considered for a feasibility problem on a parameter-dependent linear matrix inequality (LMI). In particular, a gradient-based and an ellipsoid-based randomized algorithms are improved by introduction of a stopping rule. The improved algorithms stop after a bounded number of iterations and this bound is of polynomial order in the problem size. When the algorithms stop, either of the following two events occurs: (i) they find with high confidence a probabilistic solution, which satisfies the given LMI for most of the parameter values;(ii) they detect in an approximate sense the non-existence of a deterministic solution, which satisfies the given LMI for all the parameter values. These results are important because the original randomized algorithms have issues to be settled on detection of convergence, on the speed of convergence, and on the assumption of feasibility. The improved algorithms can be adapted for an optimization problem constrained by a parameter-dependent LMI. A numerical example shows the efficacy of the proposed algorithms. (C) 2007 Elsevier Ltd. All rights reserved.

关键词： randomized algorithms parameter-dependent linear matrix inequalities stopping rules probabilistic solutions computational complexity optimization

来源：评论

学校读者我要写书评

暂无评论

A practical approximation algorithm for the LMS line estimator

引用

COMPUTATIONAL STATISTICS & DATA ANALYSIS 2007年第5期51卷 2461-2486页

作者： Mount, David M. Netanyahu, Nathan S. Romanik, Kathleen Silverman, Ruth Wu, Angela Y. Univ Maryland Dept Comp Sci College Pk MD 20742 USA Univ Maryland Inst Adv Comp Studies College Pk MD 20742 USA Bar Ilan Univ Dept Comp Sci Ramat Gan Israel Univ Maryland Ctr Automat Res College Pk MD 20742 USA White Oak Technol Inc Silver Spring MD USA American Univ Dept Comp Sci Washington DC 20016 USA

The problem of fitting a straight line to a finite collection of points in the plane is an important problem in statistical estimation. Robust estimators are widely used because of their lack of sensitivity to outlying data points. The least median-of-squares (LMS) regression line estimator is among the best known robust estimators. Given a set of it points in the plane, it is defined to be the line that minimizes the median squared residual or, more generally, the line that minimizes the residual of any given quantile q, where 0 < q <= 1. This problem is equivalent to finding the strip defined by two parallel lines of minimum vertical separation that encloses at least half of the points. The best known exact algorithm for this problem runs in O(n(2)) time. We consider two types of approximations, a residual approximation, which approximates the vertical height of the strip to within a given error bound epsilon(r) >= 0, and a quantile approximation, which approximates the fraction of points that lie within the strip to within a given error bound epsilon(q) >= 0. We present two randomized approximation algorithms for the LMS line estimator. The first is a conceptually simple quantile approximation algorithm, which given fixed q and epsilon(q) > 0 runs in 0(n log n) time. The second is a practical algorithm, which can solve both types of approximation problems or be used as an exact algorithm. We prove that when used as a quantile approximation, this algorithm's expected running time is O(n log(2) n). We present empirical evidence that the latter algorithm is quite efficient for a wide variety of input distributions, even when used as an exact algorithm. (c) 2006 Elsevier B.V. All rights reserved.

关键词： least median-of-squares regression robust estimation line fitting approximation algorithms randomized algorithms line arrangements

来源：评论

学校读者我要写书评

暂无评论

Exterminator: Automatically correcting memory errors with high probability

引用

ACM SIGPLAN NOTICES 2007年第6期42卷 1-11页

作者： Novark, Gene Berger, Emery D. Zorn, Benjamin G. Univ Massachusetts Dept Comp Sci Amherst MA 01003 USA Microsoft Res One Microsoft Way Redmond WA 98052 USA

Programs written in C and C++ are susceptible to memory errors, including buffer overflows and dangling pointers. These errors, which can lead to crashes, erroneous execution, and security vulnerabilities, are notoriously costly to repair. Tracking down their location in the source code is difficult, even when the full memory state of the program is available. Once the errors are finally found, fixing them remains challenging: even for critical security-sensitive bugs, the average time between initial reports and the issuance of a patch is nearly one month. We present Exterminator, a system that automatically corrects heap-based memory errors without programmer intervention. Exterminator exploits randomization to pinpoint errors with high precision. From this information, Exterminator derives runtime patches that fix these errors both in current and subsequent executions. In addition, Exterminator enables collaborative bug correction by merging patches generated by multiple users. We present analytical and empirical results that demonstrate Exterminator's effectiveness at detecting and correcting both injected and real faults.

关键词： algorithms languages reliability security DieFast Exterminator dynamic memory allocation error correction memory errors probabilistic memory safety randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient and scalable algorithms for inferring likely invariants in distributed systems

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2007年第11期19卷 1508-1523页

作者： Jiang, Guofei Chen, Haifeng Yoshihira, Kenji NEC Labs Amer Inc Princeton NJ 08540 USA

Distributed systems generate a large amount of monitoring data such as log files to track their operational status. However, it is hard to correlate such monitoring data effectively across distributed systems and along observation time for system management. In previous work, we proposed a concept named flow intensity to measure the intensity with which internal monitoring data reacts to the volume of user requests. We calculated flow intensity measurements from monitoring data and proposed an algorithm to automatically search constant relationships between flow intensities measured at various points across distributed systems. If such relationships hold all the time, we regard them as invariants of the underlying systems. Invariants can be used to characterize complex systems and support various system management tasks. However, the computational complexity of the previous invariant search algorithm is high so that it may not scale well in large systems with thousands of measurements. In this paper, we propose two efficient but approximate algorithms for inferring invariants in large-scale systems. The computational complexity of new randomized algorithms is significantly reduced, and experimental results from a real system are also included to demonstrate the accuracy and efficiency of our new algorithms.

关键词： distributed systems monitoring data time series data management invariants randomized algorithms computational complexity

来源：评论

学校读者我要写书评

暂无评论

Sampling from large matrices: An approach through geometric functional analysis

引用

JOURNAL OF THE ACM 2007年第4期54卷 6.1-6.19页

作者： Rudelson, Mark Vershynin, Roman Univ Missouri Dept Math Columbia MO 65211 USA Univ Calif Davis Davis CA 95616 USA

We study random submatrices of a large matrix A. We show how to approximately compute A from its random submatfix of the smallest possible size O (r log r) with a small error in the spectral norm, where r = parallel to A parallel to(2)(F) /parallel to A parallel to(2)(2) is the numerical rank of A. The numerical rank is always bounded F 2 by, and is a stable relaxation of, the rank of A. This yields an asymptotically optimal guarantee in an algorithm for computing low-rank approximations of A. We also prove asymptotically optimal estimates on the spectral norm and the cut-norm of random submatrices of A. The result for the cut-norm yields a slight improvement on the best-known sample complexity for an approximation algorithm for MAX-2CSP problems. We use methods of Probability in Banach spaces, in particular the law of large numbers for operator-valued random variables.

关键词： algorithms theory randomized algorithms Monte-Carlo methods massive data sets singular-value decompositions low-rank approximations

来源：评论

学校读者我要写书评

暂无评论

Probabilistic design of fault tolerant control via parameterization

引用

CIRCUITS SYSTEMS AND SIGNAL PROCESSING 2007年第3期26卷 325-351页

作者： Li, Hongbin Zhao, Qing Univ Alberta Dept Elect & Comp Engn Edmonton AB T6G 2V4 Canada

This paper studies the design of fault tolerant control systems (FTCSs) by considering random faults and two categories of design objectives. The FTCSs are modeled in a stochastic framework, resulting from the random fault process. The design objectives include a stability requirement and a probabilistic performance index. Such an index is chosen as a reliability-related criterion, which can be evaluated from a numerical procedure only but lacks analytical expressions. A parameterization procedure together with a randomization-based optimization method is developed to find a statistically optimal controller that can stabilize the system and achieve the highest reliability.

关键词： fault tolerant control reliability controller parameterization randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

An improved exact algorithm for the domatic number problem

引用

INFORMATION PROCESSING LETTERS 2007年第3期101卷 101-106页

作者： Riege, Tobias Rothe, Joerg Spakowski, Holger Yamamoto, Masaki Univ Dusseldorf Inst Informat D-4000 Dusseldorf Germany Tokyo Inst Technol Dept Math & Comp Sci Tokyo 152 Japan

The 3-domatic number problem asks whether a given graph can be partitioned into three dominating sets. We prove that this problem can be solved by a deterministic algorithm in time 2.695(n) (up to polynomial factors) and in polynomial space. This result improves the previous bound of 2.8805(n), which is due to Bjorklund and Husfeldt. To prove our result, we combine an algorithm by Fomin et al. with Yamamoto's algorithm for the satisfiability problem. In addition, we show that the 3-domatic number problem can be solved for graphs G with bounded maximum degree Delta (G) by a randomized polynomial-space algorithm, whose running time is better than the previous bound due to Riege and Rothe whenever Delta (G) >= 5. Our new randomized algorithm employs Schoning's approach to constraint satisfaction problems. (c) 2006 Elsevier B.V. All rights reserved.

关键词： graph algorithms exact algorithms randomized algorithms domatic number problem

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：