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

Metric Decompositions of Path-Separable Graphs

ALGORITHMICA 2017年第3期79卷 645-653页

作者： Kamma, Lior Krauthgamer, Robert Weizmann Inst Sci Rehovot Israel

A prominent tool in many problems involving metric spaces is a notion of randomized low-diameter decomposition. Loosely speaking, beta-decomposition refers to a probability distribution over partitions of the metric into sets of low diameter, such that nearby points (parameterized by beta>0) are likely to be "clustered" together. Applying this notion to the shortest-path metric in edge-weighted graphs, it is known that n-vertex graphs admit an O(ln n)-padded decomposition (Bartal, 37th annual symposium on foundations of computer science. IEEE, pp 184-193, 1996), and that excluded-minor graphs admit O(1)-padded decomposition (Klein et al., 25th annual ACM symposium on theory of computing, pp 682-690, 1993;Fakcharoenphol and Talwar, J Comput Syst Sci 69(3), 485-497, 2004;Abraham et al., Proceedings of the 46th annual ACM symposium on theory of computing. STOC '14, pp 79-88. ACM, New York, NY, USA, 2014). We design decompositions to the family of p-path-separable graphs, which was defined by Abraham and Gavoille (Proceedings of the twenty-fifth annual acm symposium on principles of distributed computing, PODC '06, pp 188-197, 2006) and refers to graphs that admit vertex-separators consisting of at most p shortest paths in the graph. Our main result is that every p-path-separable n-vertex graph admits an o(ln(p ln n))-decomposition, which refines the o(ln n) bound for general graphs, and provides new bounds for families like bounded-treewidth graphs. Technically, our clustering process differs from previous ones by working in (the shortest-path metric of) carefully chosen subgraphs.

关键词： Path-separable graphs Padded metric decomposition randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Fast deterministic consensus in a noisy environment

引用

JOURNAL OF algorithms-COGNITION INFORMATICS AND LOGIC 2002年第1期45卷 16-39页

作者： Aspnes, J Yale Univ Dept Comp Sci New Haven CT 06520 USA

It is well known that the consensus problem cannot be solved deterministically in an asynchronous environment, but that randomized solutions are possible. We propose a new model, called noisy scheduling, in which an adversarial schedule is perturbed randomly, and show that in this model randomness in the environment can substitute for randomness in the algorithm. In particular, we show that a simplified, deterministic version of Chandra's wait-free shared-memory consensus algorithm [Chandra, in: Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing, Philadelphia, PA, USA, 23-26 May, 1996, pp. 166-175] solves consensus in time at most logarithmic in the number of active processes. The proof of termination is based on showing that a race between independent delayed renewal processes produces a winner quickly. In addition, we show that the protocol finishes in constant time using quantum and priority-based scheduling on a uniprocessor, suggesting that it is robust against the choice of model over a wide range. (C) 2002 Elsevier Science (USA). All rights reserved.

关键词： consensus agreement protocols randomized algorithms distributed computing wait-free shared memory perturbation analysis noisy scheduling

来源：评论

学校读者我要写书评

暂无评论

A random coordinate descent algorithm for optimization problems with composite objective function and linear coupled constraints

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2014年第2期57卷 307-337页

作者： Necoara, Ion Patrascu, Andrei Univ Politeh Bucharest Automat Control & Syst Engn Dept Bucharest 060042 Romania

In this paper we propose a variant of the random coordinate descent method for solving linearly constrained convex optimization problems with composite objective functions. If the smooth part of the objective function has Lipschitz continuous gradient, then we prove that our method obtains an I mu-optimal solution in iterations, where n is the number of blocks. For the class of problems with cheap coordinate derivatives we show that the new method is faster than methods based on full-gradient information. Analysis for the rate of convergence in probability is also provided. For strongly convex functions our method converges linearly. Extensive numerical tests confirm that on very large problems, our method is much more numerically efficient than methods based on full gradient information.

关键词： Coordinate descent Composite objective function Linearly coupled constraints randomized algorithms Convergence rate O(1/epsilon)

来源：评论

学校读者我要写书评

暂无评论

ON THE POWER OF RANDOMIZATION IN ONLINE algorithms

引用

ALGORITHMICA 1994年第1期11卷 2-14页

作者： BENDAVID, S BORODIN, A KARP, R TARDOS, G WIGDERSON, A UNIV TORONTO DEPT COMP SCI TORONTO M5S 1A4 ON CANADA UNIV CALIF BERKELEY BERKELEY CA 94720 USA INT COMP SCI INST BERKELEY CA 94704 USA EOTVOS LORAND UNIV H-1364 BUDAPEST HUNGARY HEBREW UNIV JERUSALEM JERUSALEM ISRAEL

Against in adaptive adversary, we show that the power of randomization in on-line algorithms is severely limited! We prove the existence of an efficient ''simulation'' of randomized on-line algorithms by deterministic ones, which is best possible in general. The proof of the upper bound is existential. We deal with the issue of computing the efficient deterministic algorithm, and show that this is possible in very general cases.

关键词： ONLINE algorithms COMPETITIVE ANALYSIS randomized algorithms GAME THEORY

来源：评论

学校读者我要写书评

暂无评论

Fitness Probability Distribution of Bit-Flip Mutation

引用

EVOLUTIONARY COMPUTATION 2015年第2期23卷 217-248页

作者： Chicano, Francisco Sutton, Andrew M. Whitley, L. Darrell Alba, Enrique Univ Malaga Dept Lenguajes & Ciencias Computac E-29071 Malaga Spain Univ Jena Fak Math & Informat D-07745 Jena Germany Colorado State Univ Dept Comp Sci Ft Collins CO 80523 USA

Bit-flip mutation is a common mutation operator for evolutionary algorithms applied to optimize functions over binary strings. In this paper, we develop results from the theory of landscapes and Krawtchouk polynomials to exactly compute the probability distribution of fitness values of a binary string undergoing uniform bit-flip mutation. We prove that this probability distribution can be expressed as a polynomial in p, the probability of flipping each bit. We analyze these polynomials and provide closed-form expressions for an easy linear problem (Onemax), and an NP-hard problem, MAX-SAT. We also discuss a connection of the results with runtime analysis.

关键词： Bit-flip mutation evolutionary algorithms landscape theory combinatorial optimization randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Better algorithms for unfair metrical task systems and applications

引用

SIAM JOURNAL ON COMPUTING 2003年第6期32卷 1403-1422页

作者： Fiat, A Mendel, M Tel Aviv Univ Sch Comp Sci IL-69978 Tel Aviv Israel

Unfair metrical task systems are a generalization of online metrical task systems. In this paper we introduce new techniques to combine algorithms for unfair metrical task systems and apply these techniques to obtain ... 详细信息

关键词： online algorithms randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Parallel complexity of computations with general and Toeplitz-like matrices filled with integers and extensions

引用

SIAM JOURNAL ON COMPUTING 2000年第4期30卷 1080-1125页

作者： Pan, VY CUNY Herbert H Lehman Coll Dept Math & Comp Sci Bronx NY 10468 USA

Computations with Toeplitz and Toeplitz-like matrices are fundamental for many areas of algebraic and numerical computing. The list of computational problems reducible to Toeplitz and Toeplitz-like computations includes, in particular, the evaluation of the greatest common divisor (gcd), the least common multiple (lcm), and the resultant of two polynomials, computing Pade approximation and the Berlekamp-Massey recurrence coefficients, as well as numerous problems reducible to these. Transition to Toeplitz and Toeplitz-like computations is currently the basis for the design of the parallel randomized NC (RNC) algorithms for these computational problems. Our main result is in constructing nearly optimal randomized parallel algorithms for Toeplitz and Toeplitz-like computations and, consequently, for numerous related computational problems ( including the computational problems listed above), where all the input values are integers and all the output values are computed exactly. This includes randomized parallel algorithms for computing the rank, the determinant, and a basis for the null-space of an n x n Toeplitz or Toeplitz-like matrix A filled with integers, as well as a solution x to a linear system A x = f if the system is consistent. Our algorithms use O ((log n) log(n log \\A\\)) parallel time and O (n log n) processors, each capable of performing (in unit time) an arithmetic operation, a comparision, or a rounding of a rational nu ber to a closest integer. The cost bounds cover the cost of the veri cation of the correctness of the output. The computations by these algorithms can be performed with the precision of O (n log \\A\\) bits, which matches the precision required in order to represent the output, except for the rank computation, where the precision of the computation decreases. The algorithms involve either a single random parameter or at most 2n - 1 parameters. The cited processor bounds are less by roughly factor n than ones supported by the known alg

关键词： parallel algorithms randomized algorithms Toeplitz matrix computations Toeplitz-like matrices polynomial gcd displacement rank computational complexity block Gauss-Jordan decomposition p-adic lifting Newton-Hensel's lifting

来源：评论

学校读者我要写书评

暂无评论

Analysis of Distributed Random Grouping for aggregate computation on wireless sensor networks with randomly changing graphs

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2008年第8期19卷 1136-1149页

作者： Chen, Jen-Yeu Hu, Jianghai Natl Dong Hwa Univ Dept Elect Engn Hualien 97401 Taiwan Purdue Univ Sch Elect & Comp Engn W Lafayette IN 47907 USA

Dynamical connection graph changes are inherent in networks such as peer-to-peer networks, wireless ad hoc networks, and wireless sensor networks. Considering the influence of the frequent graph changes is, thus, essential for precisely assessing the performance of applications and algorithms on such networks. In this paper, using stochastic hybrid systems (SHSs), we model the dynamics and analyze the performance of an epidemic-like algorithm, Distributed Random Grouping (DRG), for average aggregate computation on a wireless sensor network with dynamical graph changes. Particularly, we derive the convergence criteria and the upper bounds on the running time of the DRG algorithm for a set of graphs that are individually disconnected but jointly connected in time. An effective technique for the computation of a key parameter in the derived bounds is also developed. Numerical results and an application extended from our analytical results to control the graph sequences are presented to exemplify our analysis.

关键词： performance analysis aggregate computation sensor networks randomized algorithms distributed algorithms stochastic hybrid systems graph theory

来源：评论

学校读者我要写书评

暂无评论

MATRIX PROBING AND ITS CONDITIONING

引用

SIAM JOURNAL ON NUMERICAL ANALYSIS 2012年第1期50卷 171-193页

作者： Chiu, Jiawei Demanet, Laurent MIT Dept Math Cambridge MA 02139 USA

When a matrix A with n columns is known to be well-approximated by a linear combination of basis matrices B-1, ... , B-p, we can apply A to a random vector and solve a linear system to recover this linear combination. The same technique can be used to obtain an approximation to A(-1). A basic question is whether this linear system is well-conditioned. This is important for two reasons: a well-conditioned system means (1) we can invert it and (2) the error in the reconstruction can be controlled. In this paper, we show that if the Gram matrix of the B-j's is sufficiently well-conditioned and each B-j has a high numerical rank, then n alpha p log(2) n will ensure that the linear system is well-conditioned with high probability. Our main application is probing linear operators with smooth pseudodifferential symbols such as the wave equation Hessian in seismic imaging [L. Demanet et al., Appl. Comput. Harmonic Anal., 32 (2012), pp. 155-168]. We also demonstrate numerically that matrix probing can produce good preconditioners for inverting elliptic operators in variable media.

关键词： randomized algorithms pseudodifferential operators preconditioners conditioning system identification large deviation estimates

来源：评论

学校读者我要写书评

暂无评论

Improved artificial bee colony algorithm for global optimization

引用

INFORMATION PROCESSING LETTERS 2011年第17期111卷 871-882页

作者： Gao, Weifeng Liu, Sanyang Xidian Univ Dept Appl Math Xian 710071 Peoples R China

The artificial bee colony algorithm is a relatively new optimization technique. This paper presents an improved artificial bee colony (IABC) algorithm for global optimization. Inspired by differential evolution (DE) and introducing a parameter M. we propose two improved solution search equations, namely "ABC/best/1" and "ABC/rand/1". Then, in order to take advantage of them and avoid the shortages of them, we use a selective probability p to control the frequency of introducing "ABC/rand/1" and "ABC/best/1" and get a new search mechanism. In addition, to enhance the global convergence speed, when producing the initial population, both the chaotic systems and the opposition-based learning method are employed. Experiments are conducted on a suite of unimodal/multimodal benchmark functions. The results demonstrate the good performance of the IABC algorithm in solving complex numerical optimization problems when compared with thirteen recent algorithms. (C) 2011 Elsevier B.V. All rights reserved.

关键词： randomized algorithms Artificial bee colony algorithm Initial population Solution search equation Search mechanism

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：