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

R-LINE: A better randomized 2-server algorithm on the line

THEORETICAL COMPUTER SCIENCE 2015年 605卷 106-118页

作者： Bang, Lucas Bein, Wolfgang Larmore, Lawrence L. Univ Calif Santa Barbara Dept Comp Sci Santa Barbara CA 93106 USA Univ Nevada Dept Comp Sci Las Vegas NV 89154 USA

A randomized on-line algorithm is given for competitiveness less than 1901 against the previously best known competitiveness of IN uses a new approach and defines a potential in the 2-server problem on the line, with oblivious adversary. This improves the 155/78 approximate to 1.987 for the problem. The algorithm terms of isolation indices from T-theory. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Online algorithms randomized algorithms Server problem Algorithm design T-theory Game theory

来源：评论

学校读者我要写书评

暂无评论

A randomized algorithm for a tensor-based generalization of the singular value decomposition

引用

LINEAR ALGEBRA AND ITS APPLICATIONS 2007年第2-3期420卷 553-571页

作者： Drineas, Petros Mahoney, Michael W. Yale Univ Dept Math New Haven CT 06520 USA Rensselaer Polytech Inst Dept Comp Sci Troy NY 12180 USA

An algorithm is presented and analyzed that, when given as input a d-mode tensor A, computes an approximation (A) over tilde. The approximation (A) over tilde is computed by performing the following for each of the d modes: first, form (implicitly) a matrix by "unfolding" the tensor along that mode;then, choose columns from the matrices thus generated;and finally, project the tensor along that mode onto the span of those columns. An important issue affecting the quality of the approximation is the choice of the columns from the matrices formed by "unfolding" the tensor along each of its modes. In order to address this issue, two algorithms of independent interest are presented that, given an input matrix A and a target rank k, select columns that span a space close to the best rank k subspace of the matrix. For example, in one of the algorithms, a number c (that depends on k, an error parameter epsilon, and a failure probability delta) of columns are chosen in c independent random trials according to a nonuniform probability distribution depending on the Euclidean lengths of the columns. When this algorithm for choosing columns is used in the tensor approximation, then under appropriate assumptions bounds of the form parallel to A-A parallel to(F) <= (d)Sigma(i=1) parallel to A([i])-(A([i]))k(i) parallel to(F) +d epsilon parallel to(F)+parallel to A parallel to(F) are obtained, where A([i]) is the matrix formed by "unfolding" the tensor along the ith mode and where (A([i]))k(i) is the best rank k(i) approximation to the matrix A([i]). Each parallel to A([i]) - (A([i]))k(i) parallel to(F) term is a measure of the extent to which the matrix A([i]) is not well-approximated by a rank-k(i) matrix, and the epsilon parallel to A parallel to(F) term is a measure of the loss in approximation quality due to the choice of columns (rather than, e.g., the top k(i) singular vectors along each mode). Bounds of a similar form are obtained with the other column selection algorithm.

关键词： tensor decomposition CUR decomposition randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Vectorizations of randomized matching for run-length coded strings

引用

PATTERN RECOGNITION LETTERS 1997年第1期18卷 63-72页

作者： Chung, KL Yan, WM NATL TAIWAN UNIV DEPT COMP SCI & INFORMAT ENGNTAIPEI 10764TAIWAN

Matching run-length coded strings (RLCSs) is very important in the field of pattern recognition. This paper considers the design of vectorized matching algorithms that operate directly on RLCSs. We first modify the algorithm of Karp and Rabin (1987) to design a linear-time randomized matching algorithm for RLCSs. Following this algorithm, two new and fast vectorized algorithms are presented. The first one is off-line and the second one is on-line. Some experiments are carried out on a GRAY X-MP EA/116se vector supercomputer to demonstrate the good performance of our vectorized algorithms. (C) 1997 Elsevier Science B.V.

关键词： pattern matching randomized algorithms vectorized algorithms run-length coded strings error probability vector supercomputer

来源：评论

学校读者我要写书评

暂无评论

A randomized approximation algorithm for the minimal-norm static-output-feedback problem

引用

AUTOMATICA 2016年 63卷 221-234页

作者： Peretz, Yossi (Joseph) Jerusalem Coll Technol Dept Comp Sci Lev Acad Ctr POB 16031 Jerusalem Israel

A new randomized algorithm is suggested, for extracting static-output-stabilizing-feedbacks, with approximately minimal-norm, for LTI systems. The algorithm has two similar stages, where in the first one the feasibility problem is solved, and in the second one the optimization problem is solved. The formulation is unified for the feasibility and for the optimization problems, as well as for continuous-time or discrete-time systems. The method is demonstrated by applying it to the hard (conjectured to be NP-hard) problem of the minimal-gain static-output-stabilizing-feedback, and to the hard (conjectured to be NP-hard) problem of regional pole-placement via static-output-feedback in non-convex or unconnected regions. A proof of convergence (in probability) that captures the two rounds of the algorithm is given, and complexity analysis is provided, under some mild assumptions. (C) 2015 Elsevier Ltd. All rights reserved.

关键词： Linear systems State-space representation Feedback-stability Static output feedbacks Pole-placement Approximation algorithms randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Tight Bounds for Asynchronous randomized Consensus

引用

JOURNAL OF THE ACM 2008年第5期55卷 20:1-20:26页

作者： Attiya, Hagit Censor, Keren Technion Israel Inst Technol IL-32000 Haifa Israel

A distributed consensus algorithm allows n processes to reach a common decision value starting from individual inputs. Wait-free consensus, in which a process always terminates within a finite number of its own steps, is impossible in an asynchronous shared-memory system. However, consensus becomes solvable using randomization when a process only has to terminate with probability 1. randomized consensus algorithms are typically evaluated by their total step complexity, which is the expected total number of steps taken by all processes. This article proves that the total step complexity of randomized consensus is Theta(n(2)) in an asynchronous shared memory system using multi-writer multi-reader registers. This result is achieved by improving both the lower and the upper bounds for this problem. In addition to improving upon the best previously known result by a factor of log(2) n, the lower bound features a greatly streamlined proof. Both goals are achieved through restricting attention to a set of layered executions and using an isoperimetric inequality for analyzing their behavior. The matching algorithm decreases the expected total step complexity by a log n factor, by leveraging the multi-writing capability of the shared registers. Its correctness proof is facilitated by viewing each execution of the algorithm as a stochastic process and applying Kolmogorov's inequality.

关键词： algorithms Theory Distributed computing shared-memory lower bound randomized algorithms isoperimetric inequality

来源：评论

学校读者我要写书评

暂无评论

The correctness proof of Ben-Or's randomized consensus algorithm

引用

DISTRIBUTED COMPUTING 2012年第5期25卷 371-381页

作者： Aguilera, Marcos K. Toueg, Sam Microsoft Res Silicon Valley Mountain View CA 94043 USA Univ Toronto Toronto ON M5S 3G4 Canada

In a ground-breaking paper that appeared in 1983, Ben-Or presented the first randomized algorithm to solve consensus in an asynchronous message-passing system where processes can fail by crashing. Although more efficient randomized algorithms were subsequently proposed, Ben-Or's algorithm is still the simplest and most elegant one. For this reason, it is often taught in distributed computing courses and it appears in several textbooks. Even though Ben-Or's algorithm is widely known and it is very simple, surprisingly a proof of correctness of the algorithm has not yet appeared: previously published proofs make some simplifying assumptions-specifically, they either assume that f < n/3 (n is the total number of processes and f is maximum number of processes that may crash) or that the adversary is weak, that is, it cannot see the process states or the content of the messages. In this paper, we present a correctness proof for Ben-Or's randomized consensus algorithm for the case that f < n/2 process crashes and the adversary is strong (i.e., it can see the process states and message contents, and schedule the process steps and message receipts accordingly). To the best of our knowledge, this is the first full proof of this classical algorithm. We also demonstrate a counterintuitive problem that may occur if one uses the well-known abstraction of a "global coin" to modularize and speed up randomized consensus algorithms, such as Ben-Or's algorithm. Specifically, we show that contrary to common belief, the use of a global coin can sometimes be deleterious rather than beneficial: instead of speeding up Ben-Or's algorithm, the use of a global coin in this algorithm may actually prevent termination.

关键词： process state randomized algorithms algorithms correctness of algorithm Proof of correctness Crash Speeding Coin RANDOMISING

来源：评论

学校读者我要写书评

暂无评论

randomized INTERPOLATION AND APPROXIMATION OF SPARSE POLYNOMIALS

引用

SIAM JOURNAL ON COMPUTING 1995年第2期24卷 357-368页

作者： MANSOUR, Y IBM CORP THOMAS J WATSON RES CTRYORKTOWN HTSNY 10598 HARVARD UNIV AIKEN COMPUTAT LABCAMBRIDGEMA 02138

We present a randomized algorithm that interpolates a sparse polynomial in polynomial time in the bit complexity model. The algorithm can be also applied to approximate polynomials that can be approximated by sparse p... 详细信息

关键词： POLYNOMIAL INTERPOLATION randomized algorithms APPROXIMATION HARMONIC ANALYSIS

来源：评论

学校读者我要写书评

暂无评论

randomized METHODS FOR RANK-DEFICIENT LINEAR SYSTEMS

引用

ELECTRONIC TRANSACTIONS ON NUMERICAL ANALYSIS 2015年 44卷 177-188页

作者： Sifuentes, Josef Gimbutas, Zydrunas Greengard, Leslie Texas A&M Univ Dept Math College Stn TX 77843 USA Natl Inst Stand & Technol Informat Technol Lab Boulder CO 80305 USA Simons Ctr Data Anal New York NY 10010 USA NYU Courant Inst Math Sci New York NY 10012 USA

We present a simple, accurate method for solving consistent, rank-deficient linear systems, with or without additional rank-completing constraints. Such problems arise in a variety of applications such as the computation of the eigenvectors of a matrix corresponding to a known eigenvalue. The method is based on elementary linear algebra combined with the observation that if the matrix is rank-k deficient, then a random rank-k perturbation yields a nonsingular matrix with probability close to 1.

关键词： rank-deficient systems null space null vectors eigenvectors randomized algorithms integral equations

来源：评论

学校读者我要写书评

暂无评论

An improved, randomized algorithm for parallel selection with an experimental study

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2004年第9期64卷 1051-1059页

作者： Bader, DA Univ New Mexico Dept Elect & Comp Engn Albuquerque NM 87131 USA

A common statistical problem is that of finding the median element in a set of data. This paper presents an efficient randomized high-level parallel algorithm for finding the median given a set of elements distributed across a parallel machine. In fact, our algorithm solves the general selection problem that requires the determination of the element of rank k, for an arbitrarily given integer k. Our general framework is an SPMD distributed-memory programming model that is enhanced by a set of communication primitives. We use efficient techniques for distributing and coalescing data as well as efficient combinations of task and data parallelism. The algorithms have been coded in the message-passing standard MPI, and our experimental results from the IBM SP-2 illustrate the scalability and efficiency of our algorithm and improve upon all the related experimental results known to the author. The main contributions of this paper are (1) New techniques for speeding the performance of certain randomized algorithms, such as selection, which are efficient with likely probability. (2) A new, practical randomized selection algorithm (UltraFast) with significantly improved convergence. (C) 2004 Elsevier Inc. All rights reserved.

关键词： selection algorithm randomized algorithms parallel algorithms experimental parallel algorithmics

来源：评论

学校读者我要写书评

暂无评论

A new randomized algorithm for detecting lines

引用

REAL-TIME IMAGING 2001年第6期7卷 473-481页

作者： Chen, TC Chung, KL Natl Taiwan Univ Sci & Technol Inst Comp Sci & Informat Engn Dept Informat Management Taipei 10672 Taiwan Chung Yu Jr Coll Business Adm Dept Informat Management Chilung 201 Taiwan

Line detection is very important in image processing. In this paper, a new randomized algorithm for detecting lines is presented. The proposed algorithm is quite different from the previous parameter-based methods which vote on the parameter space. Our proposed novel algorithm does not need extra storage to maintain an accumulator array for representing parameter space. The main concept used in the proposed algorithm is that we first randomly select three edge points in the image and use a distance criterion to determine whether there is a candidate line in the image;after finding that candidate line, we apply an evidence-collecting process to further determine whether the candidate line is the desired line. Some experiments have been carried out to demonstrate the computational and robust advantages of the proposed algorithm when compared with the previous algorithms. (C) 2001 Academic Press.

关键词： on line detection Image processing randomized algorithms images algorithms Afterimage parameter space methods

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：