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

A randomized linear-work EREW PRAM algorithm to find a minimum spanning forest

ALGORITHMICA 2003年第3期35卷 257-268页

作者： Poon, CK Ramachandran, V City Univ Hong Kong Dept Comp Sci Kowloon Hong Kong Peoples R China Univ Texas Dept Comp Sci Austin TX 78712 USA

We present a randomized EREW PRAM algorithm to find a minimum spanning forest in a weighted undirected graph. On an n-vertex graph the algorithm runs in o((log n)(1+epsilon)) expected time for any epsilon > 0 and performs linear expected work. This is the first linear-work, polylog-time algorithm on the EREW PRAM for this problem. This also gives parallel algorithms that perform expected linear work on two general-purpose models of parallel computation-the QSM and the BSP.

关键词： parallel algorithms minimum spanning tree EREW PRAM design of algorithms randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

THE BIT COMPLEXITY OF randomized LEADER ELECTION ON A RING

引用

SIAM JOURNAL ON COMPUTING 1989年第1期18卷 12-29页

作者： ABRAHAMSON, K ADLER, A GELBART, R HIGHAM, L KIRKPATRICK, D UNIV BRITISH COLUMBIA DEPT MATHVANCOUVER V6T 1W5BCCANADA

The inherent bit complexity of leader election on asynchronous unidirectional rings of processors is examined under various assumptions about global knowledge of the ring. If processors have unique identities with a maximum of m bits, then the expected number of communication bits sufficient to elect a leader with probability 1, on a ring of (unknown) size n is

O (n m)

来源：评论

学校读者我要写书评

暂无评论

A new randomized algorithm for group testing with unknown number of defective items

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2015年第1期30卷 150-159页

作者： Cheng, Yongxi Guo, Jue Zheng, Feifeng Xi An Jiao Tong Univ Sch Management Xian 710049 Peoples R China State Key Lab Mfg Syst Engn Xian 710049 Peoples R China Donghua Univ Glorious Sun Sch Business & Management Shanghai 200051 Peoples R China

In many fault detection problems, we want to identify defective items from a set of items using the minimum number of tests. Group testing is for the scenario where each test is on a subset of items, and tells whether the subset contains at least one defective item or not. In practice, the number of defective items is often unknown in advance. In this paper, we propose a new randomized group testing algorithm RPT (randomized Parallel Testing) for the case where the number of defective items is unknown in advance, such that with high probability , the total number of tests performed by RPT is bounded from the above by . If for some constant , which holds for most practical applications, this upper bound is asymptotically smaller than previous best result. In addition, we give a new upper bound on , the minimum number of tests required in the worst case to identify all the defective items out of items when the value of is known in advance.

关键词： Fault detection Group testing randomized algorithms Approximation

来源：评论

学校读者我要写书评

暂无评论

A Structure-Driven randomized Algorithm for the K-Center Problem

引用

IEEE LATIN AMERICA TRANSACTIONS 2015年第3期13卷 746-752页

作者： Garcia, J. Menchaca, R. Menchaca, R. Quintero, R. Inst Politecn Nacl Ctr Invest Computac Mexico City DF Mexico

In this paper we present a new randomized approximation algorithm for the metric discrete k-center problem. The main idea is to apply random perturbations to the decisions made by a deterministic approximation algorithm in such a way as to keep the approximation guarantees with high probability, but at the same time explore an extended neighborhood of the solutions produced by the deterministic approximation algorithm. We formally characterize the proposed algorithm and show that it produces 2-approximated solutions with probability of at least 1 - 1/N when it is repeated at least alpha 1nN times. alpha, N is an element of Z(+) are user-defined parameters where a measures the size of the perturbations. Experimental results show that the proposed algorithm performs similar or better than a representative set of algorithms for the k-center problem and a GRASP algorithm, which is a popular state-of-the-art technique for randomizing deterministic algorithms. Our experiments also show that the quality of the solutions found by the proposed algorithm increases faster with the number of iterations and hence, is better suited for big instances where the execution of each iteration is very expensive.

关键词： k-center selection problem NP-Hard randomized algorithms approximation algorithms GRASP

来源：评论

学校读者我要写书评

暂无评论

Subspace-Orbit randomized Decomposition for Low-Rank Matrix Approximations

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2018年第16期66卷 4409-4424页

作者： Kaloorazi, Maboud Farzaneh de lamare, Rodrigo C. Pontifical Univ Catholic Rio de Janeiro Ctr Telecommun Studies BR-22451000 Rio De Janeiro Brazil Univ York Dept Elect York YO10 5DD N Yorkshire England

An efficient, accurate, and reliable approximation of a matrix by one of lower rank is a fundamental task in numerical linear algebra and signal processing applications. In this paper, we introduce a newmatrix decomposition approach termed subspace-orbit randomized singular value decomposition (SOR-SVD), which makes use of random sampling techniques to give a low-rank approximation to an input matrix. Given a large and dense data matrix of sizem x n, the algorithm requires a few passes through data to compute a rank-k approximation in O(mnk) floating-point operations. Moreover, the SOR-SVD algorithm can utilize advanced computer architectures and, as a result, it can be optimized for maximum efficiency. The SOR-SVD algorithm is simple, accurate, and provably correct, and outperforms previously reported techniques in terms of accuracy and efficiency. Our numerical experiments support these claims.

关键词： Matrix computations dimension reduction low-rank approximation randomized algorithms robust PCA

来源：评论

学校读者我要写书评

暂无评论

Teaching randomized learners with feedback

引用

INFORMATION AND COMPUTATION 2011年第3期209卷 296-319页

作者： Balbach, Frank J. Zeugmann, Thomas Hokkaido Univ Div Comp Sci Sapporo Hokkaido 0600814 Japan Pattern Sci AG Freigericht Germany

The present paper introduces a new model for teaching randomized learners. Our new model, though based on the classical teaching dimension model, allows to study the influence of the learner's memory size and of the presence or absence of feedback. Moreover, in the new model the order in which examples are presented may influence the teaching process. The resulting models are related to Markov decision processes, and characterizations of optimal teachers for memoryless learners with feedback and for learners with infinite memory and feedback are shown. Furthermore, in the new model it is possible to investigate new aspects of teaching like teaching from positive data only or teaching with inconsistent teachers. Characterization theorems for teachability from positive data for both ordinary teachers and inconsistent teachers with and without feedback are provided. (C) 2010 Elsevier Inc. All rights reserved.

关键词： Algorithmic teaching randomized algorithms Computational complexity

来源：评论

学校读者我要写书评

暂无评论

A New randomized Block-Coordinate Primal-Dual Proximal Algorithm for Distributed Optimization

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2019年第10期64卷 4050-4065页

作者： Latafat, Puya Freris, Nikolaos M. Patrinos, Panagiotis Katholieke Univ Leuven Dept Elect Engn ESAT STADIUS B-3001 Leuven Belgium IMT Sch Adv Studies Lucca I-55100 Lucca Italy Univ Sci & Technol China Sch Comp Sci & Technol Hefei 230000 Anhui Peoples R China

This paper proposes Triangularly Preconditioned Primal- Dual algorithm, a new primal-dual algorithm for minimizing the sum of a Lipschitz-differentiable convex function and two possibly nonsmooth convex functions, one of which is composed with a linear mapping. We devise a randomized block-coordinate ( BC) version of the algorithm which converges under the same stepsize conditions as the full algorithm. It is shown that both the original as well as the BC scheme feature linear convergence rate when the functions involved are either piecewise linear-quadratic, or when they satisfy a certain quadratic growth condition (which is weaker than strong convexity). Moreover, we apply the developed algorithms to the problem of multiagent optimization on a graph, thus obtaining novel synchronous and asynchronous distributed methods. The proposed algorithms are fully distributed in the sense that the updates and the stepsizes of each agent only depend on local information. In fact, no prior global coordination is required. Finally, we showcase an application of our algorithm in distributed formation control.

关键词： Asynchronous algorithms block-coordinate (BC) minimization distributed optimization primal-dual algorithms randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

randomized load balancing by joining and splitting bins

引用

INFORMATION PROCESSING LETTERS 2012年第8-9期112卷 309-313页

作者： Aspnes, James Yin, Yitong Nanjing Univ State Key Lab Novel Software Technol Nanjing Jiangsu Peoples R China Yale Univ Dept Comp Sci New Haven CT 06520 USA

We analyze the performance of a very natural randomized load balancing scheme: uniformly joining and splitting weighted bins. We develop a norm-based technique for analyzing this simple procedure. By applying the technique, we prove several bounds for the expected load factor. Specifically, if we keep uniformly splitting the bins without joining them, the expected load factor is between Omega(n(0.5)) and O(n(0.742)), however, if we alternatively join and split bins, the expected load factor converges to O(n(1/root 1/2 log2 n)). These bounds justify the intuition that the power of being adaptive to the current loads is essential for load balancing tasks, and they also show a somehow surprising phenomenon that joins can actually help load balancing if such power is not available. (C) 2012 Elsevier B.V. All rights reserved.

关键词： randomized algorithms Load balancing

来源：评论

学校读者我要写书评

暂无评论

A randomized CUTTING PLANE METHOD WITH PROBABILISTIC GEOMETRIC CONVERGENCE

引用

SIAM JOURNAL ON OPTIMIZATION 2010年第6期20卷 3185-3207页

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

We propose a randomized method for general convex optimization problems;namely, the minimization of a linear function over a convex body. The idea is to generate N random points inside the body, choose the best one, and cut the part of the body defined by the linear constraint. We analyze the convergence properties of the algorithm from a theoretical viewpoint, i.e., under the rather standard assumption that an algorithm for uniform generation of random points in the convex body is available. Under this assumption, the expected rate of convergence for such method is proved to be geometric. This analysis is based on new results on the statistical properties of the empirical minimum over a convex body that we obtained in this paper. Moreover, explicit sample size results on convergence are derived. In particular, we compute the minimum number of random points that should be generated at each step in order to guarantee that, in a probabilistic sense, the method performs better than the deterministic center-of-gravity algorithm. From a practical viewpoint, we show how the method can be implemented using hit-and-run versions of Markov-chain Monte Carlo algorithms and exemplify the performance of this implementable modification via a number of illustrative problems. A crucial notion for the hit-and-run implementation is that of boundary oracle, which is available for most optimization problems including linear matrix inequalities and many other kinds of constraints. Preliminary numerical results for semidefinite programs are presented confirming that the randomized approach might be competitive to modern deterministic convex optimization methods.

关键词： convex optimization randomized algorithms hit-and-run linear matrix inequalities

来源：评论

学校读者我要写书评

暂无评论

A randomized Block Sampling Approach to Canonical Polyadic Decomposition of Large-Scale Tensors

引用

IEEE JOURNAL OF SELECTED TOPICS IN SIGNAL PROCESSING 2016年第2期10卷 284-295页

作者： Vervliet, Nico De Lathauwer, Lieven Katholieke Univ Leuven Dept Elect Engn ESAT B-3001 Louvain Belgium iMinds Med IT B-3000 Louvain Belgium KU Leuven Kulak Grp Sci Engn & Technol B-8500 Kortrijk Belgium

For the analysis of large-scale datasets one often assumes simple structures. In the case of tensors, a decomposition in a sum of rank-1 terms provides a compact and informative model. Finding this decomposition is intrinsically more difficult than its matrix counterpart. Moreover, for large-scale tensors, computational difficulties arise due to the curse of dimensionality. The randomized block sampling canonical polyadic decomposition method presented here combines increasingly popular ideas from randomization and stochastic optimization to tackle the computational problems. Instead of decomposing the full tensor at once, updates are computed from small random block samples. Using step size restriction the decomposition can be found up to near optimal accuracy, while reducing the computation time and number of data accesses significantly. The scalability is illustrated by the decomposition of a synthetic 8 TB tensor and a real life 12.5 GB tensor in a few minutes on a standard laptop.

关键词： Tensor decomposition canonical polyadic decomposition CANDECOMP/PARAFAC randomized algorithms block sampling big data blind source separation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：