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

A decentralized flow redistribution algorithm for avoiding cascaded failures in complex networks

PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS 2013年第23期392卷 6135-6145页

作者： Al-Takrouri, Saleh Savkin, Andrey V. Univ New S Wales Sch Elect Engn & Telecommun Sydney NSW 2052 Australia Palestine Polytech Univ West Bank Israel

A decentralized random algorithm for flow distribution in complex networks is proposed. The aim is to maintain the maximum flow while satisfying the flow limits of the nodes and links in the network. The algorithm is also used for flow redistribution after a failure in (or attack on) a complex network to avoid a cascaded failure while maintaining the maximum flow in the network. The proposed algorithm is based only on the information about the closest neighbours of each node. A mathematically rigorous proof of convergence with probability 1 of the proposed algorithm is provided. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Complex networks Cascaded failure Maximum flow Distributed algorithms randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

A random projection approach for estimation of the betweenness centrality measure

引用

INTELLIGENT DATA ANALYSIS 2013年第2期17卷 217-231页

作者： Zare, Hadi Mohammadpour, Adel Moradi, Parham Amirkabir Univ Technol Fac Math & Comp Sci Tehran Iran Univ Kurdistan Fac Elect & Comp Engn Sanandaj Iran

There are several potent measures for mining the relationships among actors in social network analysis. Betweenness centrality measure is extensively utilized in network analysis. However, it is quite time-consuming to compute exactly the betweenness centrality in high dimensional social networks. Applying random projection approach, an approximation algorithm for computing betweenness centrality of a given node, is proposed in this paper, for both weighted and unweighted graphs. It is proved that the proposed method works better than the existing methods to approximate the betweenness centrality measure. The proposed algorithm significantly reduces the number of single-source shortest path computations. We test the method on real-world networks and a synthetic benchmark and observe that the proposed algorithm shows very promising results based on statistical evaluation measure.

关键词： Betweenness centrality measure random projection social network mining concentration inequalities centrality indices randomized algorithms ranking

来源：评论

学校读者我要写书评

暂无评论

Stochastic model predictive control of LPV systems via scenario optimization

引用

AUTOMATICA 2013年第6期49卷 1861-1866页

作者： Calafiore, Giuseppe C. Fagiano, Lorenzo Politecn Torino Dipartimento Automat & Informat I-10129 Turin Italy Swiss Fed Inst Technol Automat Control Lab Zurich Switzerland Univ Calif Santa Barbara Dept Mech Engn Santa Barbara CA 93106 USA

A stochastic receding-horizon control approach for constrained Linear Parameter Varying discrete-time systems is proposed in this paper. It is assumed that the time-varying parameters have stochastic nature and that the system's matrices are bounded but otherwise arbitrary nonlinear functions of these parameters. No specific assumption on the statistics of the parameters is required. By using a randomization approach, a scenario-based finite-horizon optimal control problem is formulated, where only a finite number M of sampled predicted parameter trajectories ('scenarios') are considered. This problem is convex and its solution is a priori guaranteed to be probabilistically robust, up to a user-defined probability level p. The p level is linked to M by an analytic relationship, which establishes a tradeoff between computational complexity and robustness of the solution. Then, a receding horizon strategy is presented, involving the iterated solution of a scenario-based finite-horizon control problem at each time step. Our key result is to show that the state trajectories of the controlled system reach a terminal positively invariant set in finite time, either deterministically, or with probability no smaller than p. The features of the approach are illustrated by a numerical example. (C) 2013 Elsevier Ltd. All rights reserved.

关键词： Model predictive control Linear parameter-varying systems randomized algorithms Scenario optimization Random convex programs

来源：评论

学校读者我要写书评

暂无评论

Improving CUR Matrix Decomposition and the Nystrom Approximation via Adaptive Sampling

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2013年 14卷 2729-2769页

作者： Wang, Shusen Zhang, Zhihua Zhejiang Univ Coll Comp Sci & Technol Hangzhou 310027 Zhejiang Peoples R China Shanghai Jiao Tong Univ Dept Comp Sci & Engn Shanghai 200240 Peoples R China

The CUR matrix decomposition and the Nystrom approximation are two important low-rank matrix approximation techniques. The Nystrom method approximates a symmetric positive semidefinite matrix in terms of a small number of its columns, while CUR approximates an arbitrary data matrix by a small number of its columns and rows. Thus, CUR decomposition can be regarded as an extension of the Nystrom approximation. In this paper we establish a more general error bound for the adaptive column/row sampling algorithm, based on which we propose more accurate CUR and Nystrom algorithms with expected relative-error bounds. The proposed CUR and Nystrom algorithms also have low time complexity and can avoid maintaining the whole data matrix in RAM. In addition, we give theoretical analysis for the lower error bounds of the standard Nystrom method and the ensemble Nystrom method. The main theoretical results established in this paper are novel, and our analysis makes no special assumption on the data matrices.

关键词： large-scale matrix computation CUR matrix decomposition the Nystrom method randomized algorithms adaptive sampling

来源：评论

学校读者我要写书评

暂无评论

Robust Model Predictive Control via Scenario Optimization

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2013年第1期58卷 219-224页

作者： Calafiore, Giuseppe C. Fagiano, Lorenzo Politecn Torino Dipartimento Automat & Informat I-10129 Turin Italy Univ Calif Santa Barbara Dept Mech Engn Santa Barbara CA 93106 USA

This paper discusses a novel probabilistic approach for the design of robust model predictive control (MPC) laws for discrete-time linear systems affected by parametric uncertainty and additive disturbances. The proposed technique is based on the iterated solution, at each step, of a finite-horizon optimal control problem (FHOCP) that takes into account a suitable number of randomly extracted scenarios of uncertainty and disturbances, followed by a specific command selection rule implemented in a receding horizon fashion. The scenario FHOCP is always convex, also when the uncertain parameters and disturbance belong to nonconvex sets, and irrespective of how the model uncertainty influences the system's matrices. Moreover, the computational complexity of the proposed approach does not depend on the uncertainty/disturbance dimensions, and scales quadratically with the control horizon. The main result in this work is related to the analysis of the closed loop system under receding-horizon implementation of the scenario FHOCP, and essentially states that the devised control law guarantees constraint satisfaction at each step with some a priori assigned probability p, while the system's state reaches the target set either asymptotically, or in finite time with probability at least p. The proposed method may be a valid alternative when other existing techniques, either deterministic or stochastic, are not directly usable due to excessive conservatism or to numerical intractability caused by lack of convexity of the robust or chance-constrained optimization problem.

关键词： Model predictive control (MPC) randomized algorithms robustness scenario optimization

来源：评论

学校读者我要写书评

暂无评论

An output-sensitive algorithm for persistent homology

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2013年第4期46卷 435-447页

作者： Chen, Chao Kerber, Michael IST Austria Klosterneuburg Austria

In this paper, we present the first output-sensitive algorithm to compute the persistence diagram of a filtered simplicial complex. For any Gamma > 0, it returns only those homology classes with persistence at least Gamma. Instead of the classical reduction via column operations, our algorithm performs rank computations on submatrices of the boundary matrix. For an arbitrary constant delta is an element of (0, 1), the running time is O (C(1-delta)Gamma Rd(n) log n), where C(1-delta)Gamma is the number of homology classes with persistence at least (1 - delta)Gamma, n is the total number of simplices in the complex, d its dimension, and R-d(n) is the complexity of computing the rank of an n x n matrix with O (dn) nonzero entries. Depending on the choice of the rank algorithm, this yields a deterministic O (C(1-delta))(Gamma)n(2.376)) algorithm, an O (C((1-delta)Gamma)n(2.28)) Las-Vegas algorithm, or an O (C((1-delta)Gamma)n(2+epsilon)) Monte-Carlo algorithm for an arbitrary epsilon > 0. The space complexity of the Monte-Carlo version is bounded by O (dn) = O (n log n). (c) 2012 Elsevier B.V. All rights reserved.

关键词： Computational topology Persistent homology randomized algorithms Rank computation

来源：评论

学校读者我要写书评

暂无评论

Searching for a subset of counterfeit coins: Randomization vs determinism and adaptiveness vs non-adaptiveness

引用

RANDOM STRUCTURES & algorithms 2013年第1期42卷 97-109页

作者： De Marco, Gianluca Kowalski, Dariusz R. Univ Liverpool Dept Comp Sci Liverpool L69 3BX Merseyside England Univ Salerno Dipartimento Informat I-84084 Fisciano SA Italy

We are given n coins of which k are heavy (defective), while the remaining n - k are light (good). We know both the weight of the good coins and the weight of the defective ones. Therefore, if we weigh a subset Q ? S with a spring scale, then the outcome will tell us exactly the number of defectives contained in Q. The problem, known as Counterfeit Coins problem, is to identify the set of defective coins by minimizing the number of weighings, also called queries. It is well known that T(klog k +1(n/k)) queries are enough, even for non-adaptive algorithms, in case k = cn for some constant 0 < c < 1. A natural interesting generalization arises when we are required to identify any subset of m = k defectives. We show that while for randomized algorithms \documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}\begin{align*}\tilde{\Theta}(m)\end{align*} \end{document} queries are sufficient, the deterministic non-adaptive counterpart still requires T(klog k +1(n/k)) queries, in case k = n/28;therefore, finding any subset of defectives is not easier than finding all of them by a non-adaptive deterministic algorithm. (C) 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012

关键词： algorithms randomized algorithms adaptive algorithms combinatorial search counterfeit coins

来源：评论

学校读者我要写书评

暂无评论

Exploiting independent subformulas: A faster approximation scheme for #k-SAT

引用

INFORMATION PROCESSING LETTERS 2013年第9期113卷 337-344页

作者： Schmitt, Manuel Wanka, Rolf Univ Erlangen Nurnberg Dept Comp Sci D-91058 Erlangen Germany

We present an improvement on Thurley's recent randomized approximation scheme for #k-SAT where the task is to count the number of satisfying truth assignments of a Boolean function Phi given as an n-variable k-CNF. We introduce a novel way to identify independent substructures of Phi and can therefore reduce the size of the search space considerably. Our randomized algorithm works for any k. For #3-SAT, it runs in time O(epsilon(-2) . 1.51426(n)), for #4-SAT, it runs in time O(epsilon(-2) . 1.60816(n)), with error bound epsilon. (c) 2013 Elsevier B.V. All rights reserved.

关键词： algorithms Analysis of algorithms randomized algorithms #k-SAT Satisfiability

来源：评论

学校读者我要写书评

暂无评论

Fast construction of irreducible polynomials over finite fields

引用

ISRAEL JOURNAL OF MATHEMATICS 2013年第1期194卷 77-105页

作者： Couveignes, Jean-Marc Lercier, Reynald INRIA Bordeaux Sud Ouest F-31058 Toulouse 9 France Univ Toulouse 2 Univ Toulouse Dept Math & Informat F-31058 Toulouse 9 France DGA F-35174 La Roche Marguerite France Univ Rennes 1 Inst Rech Math Rennes F-35042 Rennes France

We present a randomized algorithm that on inputting a finite field K with q elements and a positive integer d outputs a degree d irreducible polynomial in K[x]. The running time is d (1+E >(d))x(log q)(5+E >(q)) elementary operations. The function E > in this expression is a real positive function belonging to the class o(1), especially, the complexity is quasi-linear in the degree d. Once given such an irreducible polynomial of degree d, we can compute random irreducible polynomials of degree d at the expense of d (1+E >(d)) x (log q)(1+E >(q)) elementary operations only.

关键词： randomized belonging polynomial Galois fields randomized algorithms Polynomial Belonging Irreducible Irreducible polynomial RANDOMISING Elementary

来源：评论

学校读者我要写书评

暂无评论

Heat Flow and A Faster Algorithm to Compute the Surface Area of A Convex Body

引用

RANDOM STRUCTURES & algorithms 2013年第4期43卷 407-428页

作者： Belkin, Mikhail Narayanan, Hariharan Niyogi, Partha Ohio State Univ Dept Comp Sci & Engn Columbus OH 43210 USA Univ Washington Dept Stat & Math Seattle WA 98195 USA Univ Chicago Dept Comp Sci Chicago IL 60637 USA

We draw on the observation that the amount of heat diffusing outside of a heated body in a short period of time is proportional to its surface area, to design a simple algorithm for approximating the surface area of a convex body given by a membership oracle. Our method has a complexity of O-*(n(4)), where n is the dimension, compared to O-*(n(8)) for the previous best algorithm. We show that our complexity cannot be improved given the current state-of-the-art in volume estimation. (c) 2013 Wiley Periodicals, Inc. Random Struct. Alg., 43, 407-428, 2013

关键词： randomized algorithms diffusion convex geometry surface area

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：