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

Efficient optimal design of uncertain discrete time dynamical systems

AUTOMATICA 2012年第10期48卷 2544-2549页

作者： Lin, Chenxi Runolfsson, Thordur Univ Oklahoma Sch Elect & Comp Engn Norman OK 73019 USA

In this paper we consider the problem of optimal design of an uncertain discrete time nonlinear dynamical system. The problem is formulated using an a-posterori design criterion, which can account for uncertainties generated by the dynamics of the system itself as well as parametric uncertainties. In general, for most uncertain complex dynamical systems, this type of method is difficult to solve analytically. A numerical scheme is developed for the optimal design that involves two steps. First, in order to obtain a numerical algorithm for the optimal solution, we apply randomized algorithms for average performance synthesis to approximate the optimal solution. Second, using the properties of the Perron-Frobenius operator we develop an efficient computation approach to calculate the stationary distribution for the uncertain dynamical systems and the average performance criteria. (C) 2012 Elsevier Ltd. All rights reserved.

关键词： Discrete time dynamical systems Uncertain parameters Optimal design randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

An improved reliability bound of a probabilistic parallel integer sorting algorithm

引用

INFORMATION PROCESSING LETTERS 2012年第24期112卷 976-979页

作者： Gerbessiotis, Alexandros V. New Jersey Inst Technol CS Dept Newark NJ 07102 USA

It is shown how one can improve the reliability bound of the parallel sorting algorithm of Rajasekaran and Sen (1992) 171 that sorts uniformly distributed integer keys on a CRCW Parallel Random Access Machine (PRAM). The probability of success improves to -> 2-(Omega(n log log n/ logn)) from the previous bound of 1 - 2(-Omega(n/logn log logn))) while retaining the (O) over tilde (logn) time bound for sorting n uniformly distributed integers on n/logn processors. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Analysis of algorithms Parallel algorithms randomized algorithms Uniformly distributed integers Integer sorting

来源：评论

学校读者我要写书评

暂无评论

Optimal Distributed Blanket Coverage Self-Deployment of Mobile Wireless Sensor Networks

引用

IEEE COMMUNICATIONS LETTERS 2012年第6期16卷 949-951页

作者： Savkin, Andrey V. Javed, Faizan Matveev, Alexey S. Univ New S Wales Sch Elect Engn & Telecommun Sydney NSW 2052 Australia

We propose a novel distributed random algorithm for self-deployment of a network of mobile wireless sensors in the problem of blanket coverage. The aim is to deploy sensors in a bounded region so that any point of the region is sensed by at least one sensor. The algorithm is based only on information about the closest neighbours of each sensor. The monitoring region is of an arbitrary shape and not known to the sensors a priori. We give mathematically rigorous proofs of asymptotic optimality and convergence with probability 1 of the proposed algorithm.

关键词： Wireless sensor networks mobile sensor networks sensor deployment distributed algorithms blanket coverage randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Practical perfect hashing in nearly optimal space

引用

INFORMATION SYSTEMS 2012年第1期38卷 108-131页

作者： Botelho, Fabiano C. Pagh, Rasmus Ziviani, Nivio Data Domain EMC Co Santa Clara CA USA Univ Fed Minas Gerais Dept Comp Sci Belo Horizonte MG Brazil IT Univ Copenhagen Copenhagen Denmark

A hash function is a mapping from a key universe U to a range of integers, i.e., h: U bar right arrow {0, 1, . . . , m-1}, where m is the range's size. A perfect hash function for some set S subset of U is a hash function that is one-to-one on S. where m >= vertical bar S vertical bar. A minimal perfect hash function for some set S subset of U is a perfect hash function with a range of minimum size, i.e., m = vertical bar S vertical bar. This paper presents a construction for (minimal) perfect hash functions that combines theoretical analysis, practical performance, expected linear construction time and nearly optimal space consumption for the data structure. For n keys and m = n the space consumption ranges from 2.62n + o(n) to 3.3n + o(n) bits, and for m = 1.23n it ranges from 1.95n + o(n) to 2.7n + o(n) bits. This is within a small constant factor from the theoretical lower bounds of 1.44n bits for m = n and 0.89n bits for m = 1.23n. We combine several theoretical results into a practical solution that has turned perfect hashing into a very compact data structure to solve the membership problem when the key set S is static and known in advance. By taking into account the memory hierarchy we can construct (minimal) perfect hash functions for over a billion keys in 46 min using a commodity PC. An open source implementation of the algorithms is available at http://*** under the GNU Lesser General Public License (LGPL). (c) 2012 Elsevier Ltd. All rights reserved.

关键词： Perfect hash functions randomized algorithms Random graphs Large key sets

来源：评论

学校读者我要写书评

暂无评论

Effect of increasing the energy gap between the two lowest energy states on the mixing time of the Metropolis algorithm

引用

INFORMATION PROCESSING LETTERS 2012年第23期112卷 922-927页

作者： Nakade, Apurv Biswas, Somenath IIT Kanpur Dept Comp Sci & Engn Kanpur 208016 Uttar Pradesh India Chennai Math Inst Kelambakkam 603103 Siruseri India

In order to understand what makes natural proteins fold rapidly. Sali, Shakhnovich and Karplus (1994) [6,7] had used the Metropolis algorithm to search for the minimum energy conformations of chains of beads in the lattice model of protein folding. Based on their computational experiments, they concluded that the Metropolis algorithm would find the minimum energy conformation of a chain of beads within an acceptable time scale if and only if there is a large gap between the energies of the minimum energy conformation and that of the second minimum. Clote (1999) [1] attempted to support this conclusion by a proof that the mixing time of the underlying Markov chain would decrease as the gap in energies of the minimum energy conformation and that of the second minimum increased. He was able to show that an upper bound on the mixing time does indeed decrease as the energy gap increases. We show in this paper that the mixing time itself, however, is a non-decreasing function of the value of the energy gap. Therefore, our result contradicts what Clote had attempted to prove. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Metropolis algorithm Markov chain mixing time Protein folding randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Constrained multilinear detection for faster functional motif discovery

引用

INFORMATION PROCESSING LETTERS 2012年第22期112卷 889-892页

作者： Koutis, Ioannis Univ Puerto Rico Dept Comp Sci Rio Piedras PR 00931 USA

The GRAPH MOTIF problem asks whether a given multiset of colors appears on a connected subgraph of a vertex-colored graph. The fastest known parameterized algorithm for this problem is based on a reduction to the k-Multilinear Detection (k-MLD) problem: the detection of multilinear terms of total degree k in polynomials presented as circuits. We revisit k-MLD and define k-CMLD, a constrained version of it which reflects GRAPH MOTIF more faithfully. We then give a fast algorithm for k-CMLD. As a result we obtain faster parameterized algorithms for GRAPH MOTIF and variants of it. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Graph algorithms randomized algorithms Parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Local correction of juntas

引用

INFORMATION PROCESSING LETTERS 2012年第6期112卷 223-226页

作者： Alon, Noga Weinstein, Amit Tel Aviv Univ Blavatnik Sch Comp Sci IL-69978 Tel Aviv Israel Tel Aviv Univ Sackler Sch Math IL-69978 Tel Aviv Israel Inst Adv Study Princeton NJ 08540 USA

A Boolean function f over n variables is said to be q-locally correctable if, given a black-box access to a function g which is "close" to an isomorphism f(sigma) of f, we can compute f(sigma) (x) for any x is an element of Z(2)(n) with good probability using q queries to g. We observe that any k-junta, that is, any function which depends only on k of its input variables, is O(2(k))-locally correctable. Moreover, we show that there are examples where this is essentially best possible, and locally correcting some k-juntas requires a number of queries which is exponential in k. These examples, however, are far from being typical, and indeed we prove that for almost every k-junta, O(k log k) queries suffice. (C) 2011 Elsevier B.V. All rights reserved.

关键词： randomized algorithms Local correction Locally correctable codes

来源：评论

学校读者我要写书评

暂无评论

Pseudorandom Generators, Typically-Correct Derandomization, and Circuit Lower Bounds

引用

COMPUTATIONAL COMPLEXITY 2012年第1期21卷 3-61页

作者： Kinne, Jeff van Melkebeek, Dieter Shaltiel, Ronen Indiana State Univ Dept Math & Comp Sci Terre Haute IN 47809 USA Univ Haifa Dept Comp Sci IL-31905 Haifa Israel Univ Wisconsin Dept Comp Sci Madison WI 53706 USA

The area of derandomization attempts to provide efficient deterministic simulations of randomized algorithms in various algorithmic settings. Goldreich and Wigderson introduced a notion of "typically-correct" deterministic simulations, which are allowed to err on few inputs. In this paper, we further the study of typically-correct derandomization in two ways. First, we develop a generic approach for constructing typically-correct derandomizations based on seed-extending pseudorandom generators, which are pseudorandom generators that reveal their seed. We use our approach to obtain both conditional and unconditional typically-correct derandomization results in various algorithmic settings. We show that our technique strictly generalizes an earlier approach by Shaltiel based on randomness extractors and simplifies the proofs of some known results. We also demonstrate that our approach is applicable in algorithmic settings where earlier work did not apply. For example, we present a typically-correct polynomial-time simulation for every language in BPP based on a hardness assumption that is (seemingly) weaker than the ones used in earlier work. Second, we investigate whether typically-correct derandomization of BPP implies circuit lower bounds. Extending the work of Kabanets and Impagliazzo for the zero-error case, we establish a positive answer for error rates in the range considered by Goldreich and Wigderson. In doing so, we provide a simpler proof of the zero-error result. Our proof scales better than the original one and does not rely on the result by Impagliazzo, Kabanets, and Wigderson that NEXP having polynomialsize circuits implies that NEXP coincides with EXP.

关键词： Typically-correct derandomization pseudorandom generators circuit lower bounds randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

FAST INFORMATION SPREADING IN GRAPHS WITH LARGE WEAK CONDUCTANCE

引用

SIAM JOURNAL ON COMPUTING 2012年第6期41卷 1451-1465页

作者： Censor-Hillel, Keren Shachnai, Hadas MIT CSAIL Cambridge MA 02139 USA Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel

Gathering data from nodes in a network is at the heart of many distributed applications, most notably while performing a global task. We consider information spreading among n nodes of a network, where each node v has a message m(v) which must be received by all other nodes. The time required for information spreading has been previously upper-bounded with an inverse relationship to the conductance of the underlying communication graph. This implies high running time bounds for graphs with small conductance. The main contribution of this paper is an information spreading algorithm which overcomes communication bottlenecks and thus achieves fast information spreading for a wide class of graphs, despite their small conductance. As a key tool in our study we use the recently defined concept of weak conductance, a generalization of classic graph conductance which measures how well-connected the components of a graph are. Our hybrid algorithm, which alternates between random and deterministic communication phases, exploits the connectivity within components by first applying partial information spreading, in which information is exchanged within well-connected components, and then sending messages across bottlenecks, thus spreading further throughout the network. This yields substantial improvements over the best known running times of algorithms for information spreading on any graph that has large weak conductance, from a polynomial to a polylogarithmic number of rounds.

关键词： distributed computing randomized algorithms weak conductance information spreading

来源：评论

学校读者我要写书评

暂无评论

QUASIRANDOM LOAD BALANCING

引用

SIAM JOURNAL ON COMPUTING 2012年第4期41卷 747-771页

作者： Friedrich, Tobias Gairing, Martin Sauerwald, Thomas Univ Jena D-07743 Jena Germany Univ Liverpool Dept Comp Sci Liverpool L69 3BX Merseyside England Max Planck Inst Informat D-66123 Saarbrucken Germany

We propose a simple distributed algorithm for balancing indivisible tokens on graphs. The algorithm is completely deterministic, though it tries to imitate (and enhance) a randomized algorithm by keeping the accumulated rounding errors as small as possible. Our new algorithm, surprisingly, closely approximates the idealized process (where the tokens are divisible) on important network topologies. On d-dimensional torus graphs with n nodes it deviates from the idealized process only by an additive constant. In contrast, the randomized rounding approach of Friedrich and Sauerwald [Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009, pp. 121-130] can deviate up to Omega(polylog(n)), and the deterministic algorithm of Rabani, Sinclair, and Wanka [Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, 1998, pp. 694-705] has a deviation of Omega(n(1/d)). This makes our quasirandom algorithm the first known algorithm for this setting, which is optimal both in time and achieved smoothness. We further show that on the hypercube as well, our algorithm has a smaller deviation from the idealized process than the previous algorithms. To prove these results, we derive several combinatorial and probabilistic results that we believe to be of independent interest. In particular, we show that first-passage probabilities of a random walk on a path with arbitrary weights can be expressed as a convolution of independent geometric probability distributions.

关键词： distributed computing load balancing randomized algorithms random walk quasirandomness

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：