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

IEEE International Conference on Acoustics, Speech and Signal Processing

作者： Michael Moldaschl Wilfried N. Gansterer Ondrej Hlinka Florian Meyer Franz Hlawatsch University of Vienna Research Group Theory and Applications of Algorithms Vienna Austria Institute of Telecommunications Vienna University of Technology Vienna Austria

ISBN: (纸本)9781479928941

Most distributed statistical signal processing methods assume conditionally uncorrelated sensor measurements although this assumption is often not satisfied. Here, we propose a distributed algorithm for decorrelating the sensor measurements in a wireless sensor network. The algorithm employs a matrix-valued Chebyshev approximation to achieve an approximate decorrelation using only local computations and communication between neighboring sensors. We apply the algorithm to consensus-based distributed particle filtering in a target tracking problem with correlated measurement noises. Simulations show that the decorrelation yields a substantial accuracy improvement while causing only a small communication overhead.

关键词： Decorrelation Chebyshev approximation Approximation algorithms Atmospheric measurements Particle measurements Vectors

来源：评论

学校读者我要写书评

暂无评论

Swarm/evolutionary intelligence for agent-based social simulation

Swarm/evolutionary intelligence for agent-based social simul...

引用

Congress on Evolutionary Computation

作者： Andreas Janecek Tobias Jordan Fernando Buarque de Lima-Neto University of Vienna Austria Research Group Theory and Applications of Algorithms University of Pernambuco Re-cifelPE Brazil Polytechnic School of Engineering/Computing Engineering Program

Several micro economic models allow to evaluate consumer's behavior using a utility function that is able to measure the success of an individual's decision. Such a decision may consist of a tuple of goods an individual would like to buy and hours of work necessary to pay for them. The utility of such a decision depends not only on purchase and consumption of goods, but also on fringe benefits such as leisure, which additionally increases the utility to the individual. Utility can be used then as a collective measure for the overall evaluation of societies. In this paper, we present and compare three different agent based social simulations in which the decision finding process of consumers is performed by three algorithms from swarm intelligence and evolutionary computation. Although all algorithms appear to be suitable for the underlying problem as they are based on historical information and also contain a stochastic part which allows for modeling the uncertainty and bounded rationality, they differ greatly in terms of incorporating historical information used for finding new alternative decisions. Newly created decisions that violate underlying budget constraints may either be mapped back to the feasible region, or may be allowed to leave the valid search space. However, in order to avoid biases that would disrupt the inner rationale of each meta heuristic, such invalid decisions are not remembered in the future. Experiments indicate that the choice of such bounding strategy varies according to the choice of the optimization algorithm. Moreover, it seems that each of the techniques could excel in identifying different types of individual behavior such as risk affine, cautious and balanced.

关键词： Optimization Frequency selective surfaces Computational modeling Biological system modeling Remuneration Economics Decision making

来源：评论

学校读者我要写书评

暂无评论

Dynamic search in fireworks algorithm

Dynamic search in fireworks algorithm

引用

Congress on Evolutionary Computation

作者： Shaoqiu Zheng Andreas Janecek Junzhi Li Ying Tan Department of Machine Intelligence Peking University Beijing P.R. China Research Group Theory and Applications of Algorithms University of Vienna Vienna Austria

We propose an improved version of the recently developed Enhanced Fireworks Algorithm (EFWA) based on an adaptive dynamic local search mechanism. In EFWA, the explosion amplitude (i.e., search area around the current location) of each firework is computed based on the quality of the firework's current location. This explosion amplitude is limited by a lower bound which decreases with the number of iterations in order to avoid the explosion amplitude to be [close to] zero, and in order to enhance global search abilities at the beginning and local search abilities towards the later phase of the algorithm. As the explosion amplitude in EFWA depends solely on the fireworks' fitness and the current number of iterations, this procedure does not allow for an adaptive optimization process. To deal with these limitations, we propose the Dynamic Search Fireworks Algorithm (dynFWA) which uses a dynamic explosion amplitude for the firework at the currently best position. If the fitness of the best firework could be improved, the explosion amplitude will increase in order to speed up convergence. On the contrary, if the current position of the best firework could not be improved, the explosion amplitude will decrease in order to narrow the search area. In addition, we show that one of the EFWA operators can be removed in dynFWA without a loss in accuracy - this makes dynFWA computationally more efficient than EFWA. Experiments on 28 benchmark functions indicate that dynFWA is able to significantly outperform EFWA, and achieves better performance than the latest SPSO version SPSO2011.

关键词： Explosions Sparks Heuristic algorithms Optimization Convergence Sociology Statistics

来源：评论

学校读者我要写书评

暂无评论

Robust gossip-based aggregation: A practical point of view 15

Robust gossip-based aggregation: A practical point of view

引用

15th Workshop on Algorithm Engineering and Experiments, ALENEX 2013

作者： Niederbrucker, Gerhard Gansterer, Wilfried N. University of Vienna Research Group Theory and Applications of Algorithms Austria

ISBN: (纸本)9781611972535

Over the last years, several gossip-based aggregation algorithms have been developed which focus on providing resilience in failure-prone distributed systems. The main objective of such algorithms is the efficient in-network computation of aggregates even in the case when system failures occur during runtime. In this paper, we evaluate performance and limitations in practical computations of those gossip-based aggregation algorithms with the most promising theoretical fault tolerance properties. Theoretical analyses of these algorithms usually address only the principal ability of handling or overcoming a certain kind of system failure. Most of the time, there are no formal results on the concrete impact of failure handling on the performance of the algorithms, e. g., in terms of convergence speed. This leaves a wide gap between theory and practice, as we illustrate in this paper. In order to bridge this gap, we first categorize common system failures of interest. Then, we experimentally investigate how well these common failure types are handled in practice by the considered algorithms and up to which extent these state-of-the-art methods provide a reasonable degree of fault tolerance in practice. Our experimental studies reveal (i) that certain failure handling approaches which work in theory exhibit unacceptable performance in practice and (ii) that in some cases the failure handling mechanisms used introduce new problems, e. g., numerical inaccuracy. Our investigations illustrate that for some failure types (such as permanent node failures) further algorithmic advances are required to achieve resilience with a reasonably small overhead and acceptable performance. Copyright © SIAM.

关键词： Fault tolerance

来源：评论

学校读者我要写书评

暂无评论

Fault Tolerance Properties of Gossip-Based Distributed Orthogonal Iteration Methods

引用

Procedia Computer Science 2013年 18卷 189-198页

作者： Hana Straková Gerhard Niederbrucker Wilfried N. Gansterer University of Vienna Research Group Theory and Applications of Algorithms Austria

In this paper, we investigate and compare the fault tolerance properties and resilience of gossip-based distributed orthog- onal iteration algorithms for the in-network computation of the extreme eigenpairs of matrix. Gossip-based algorithms have many attractive properties, especially for loosely coupled distributed and decentralized systems, like P2P networks or sensor networks. Due to their randomized communication schedule and the fact that communication happens only between nearest neighbors, they are highly flexible with respect to the topology of the underlying system. Moreover, such algorithms have a big potential for high resilience against various types of failures. Lately, several gossip-based distributed eigensolvers based on orthogonal iteration method have been introduced. However, the performance of these algorithms in the presence of failures has not been analyzed yet. We illustrate that convergence properties, the numerical accuracy achieved, as well as resilience properties of gossip-based distributed orthogonal iteration are basically determined by the choice of the distributed data aggregation algorithm (DDAA) which is required within the algorithm for performing distributed reduction operations (such as summation or averaging) across the system. In particular, we illustrate that when using the proper combination of DDAA and distributed orthogonal iteration method, high accuracy can be achieved and even silent message loss can be tolerated without any loss in numerical accuracy.

关键词： Fault tolerance Self-healing algorithm Gossip algorithms Distributed algorithm Randomized communication schedule Orthogonal iteration

来源：评论

学校读者我要写书评

暂无评论

On Mixed Precision Iterative Refinement for Eigenvalue Problems

引用

Procedia Computer Science 2013年 18卷 2647-2650页

作者： Karl E. Prikopa Wilfried N. Gansterer University of Vienna Research Group Theory and Applications of Algorithms Austria

We investigate novel iterative refinement methods for solving eigenvalue problems which are derived from Newton's method. In particular, approaches for the solution of the resulting linear system based on saddle point problems are compared and evaluated. The algorithms presented exploit the performance benefits of mixed precision, where the majority of operations are performed at a lower working precision and only critical steps within the algorithm are computed in a higher target precision, leading to a solution which is accurate to the target precision. A complexity analysis shows that the best novel method presented requires fewer floating point operations than the so far only existing iterative refinement eigensolver by Dongarra, Moler and Wilkinson.

关键词： iterative refinement eigenvalue problems mixed precision saddle point/equilibrium problems

来源：评论

学校读者我要写书评

暂无评论

A Distributed Eigensolver for Loosely Coupled Networks

A Distributed Eigensolver for Loosely Coupled Networks

引用

Euromicro Conference on Parallel, Distributed and Network-Based Processing

作者： Hana Strakova Wilfried N. Gansterer Research Group Theory and Applications of Algorithms University of Vienna Vienna Austria

We introduce a new distributed eigensolver (dOI) for square matrices based on orthogonal iteration. In contrast to standard parallel eigensolvers, our approach performs only nearest neighbor communication and provides much more flexibility with respect to the properties of the hardware infrastructure on which the computation is performed. This is achieved by utilizing distributed summation methods with randomized communication schedules which do not require global synchronization across the nodes. Our algorithm is particularly attractive for loosely coupled distributed networks with arbitrary network topologies and potentially unreliable components. Our distributed eigensolver dOI is based on a novel distributed matrix-matrix multiplication algorithm and on an extension of a distributed QR factorization algorithm proposed earlier. We illustrate the advantages of dOI in terms of higher flexibility with respect to the underlying network and lower communication cost compared to a related distributed eigensolver by Kempe and McSherry. Moreover, we experimentally illustrate how the overall communication cost of dOI is further reduced by adapting the accuracy of each distributed summation during the orthogonal iteration process.

关键词： Accuracy Topology Network topology Algorithm design and analysis Eigenvalues and eigenfunctions Signal processing algorithms Vectors

来源：评论

学校读者我要写书评

暂无评论

Graph Products Revisited: Tight Approximation Hardness of Induced Matching, Poset Dimension and More 13

Graph Products Revisited: Tight Approximation Hardness of In...

引用

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete algorithms

作者： Parinya Chalermsook Bundit Laekhanukit Danupon Nanongkai IDSIA School of Computer Science McGill University Theory and Applications of Algorithms Research Group University of Vienna

ISBN: (纸本)9781611972511

Graph product is a fundamental tool with rich applications in both graph theory and theoretical computer science. It is usually studied in the form f(G * H) where G and H are graphs, * is a graph product and f is a graph property. For example, if f is the independence number and * is the disjunctive product, then the product is known to be multiplicative: f(G * H) = f(G)f(H). In this paper, we study graph products in the following non-standard form: f((G{direct +} H)*J) where G, H and J are graphs, and * are two different graph products and f is a graph property. We show that if f is the induced and semi-induced matching number, then for some products {direct +} and *, it is subadditive in the sense that f((G{direct +} H) * J) ≤ f(G* J)+f(H * J). Moreover, when f is the poset dimension number, it is almost subadditive.

关键词： Graph Products Approximation Hardness Poset Dimension subadditive Line graph Poset Fluorine (F) iodine dimensions theoretical computer science Discrete mathematics approximation

来源：评论

学校读者我要写书评

暂无评论

An O(n2) time algorithm for alternating Büchi games

An O(n2) time algorithm for alternating Büchi games

引用

23rd Annual ACM-SIAM Symposium on Discrete algorithms, SODA 2012

作者： Chatterjee, Krishnendu Henzinger, Monika Austria Research Group Theory and Applications of Algorithms University of Vienna Austria

ISBN: (纸本)9781611972108

Computing the winning set for Büchi objectives in alternating games on graphs is a central problem in computer aided verification with a large number of applications. The long standing best known upper bound for solving the problem is Õ(n·m), where n is the number of vertices and m is the number of edges in the graph. We are the first to break the Õ(n·m) boundary by presenting a new technique that reduces the running time to O(n 2). This bound also leads to O(n2) time algorithms for computing the set of almost-sure winning vertices for Büchi objectives (1) in alternating games with probabilistic transitions (improving an earlier bound of Õ(n·m)), (2) in concurrent graph games with constant actions (improving an earlier bound of O(n3)), and (3) in Markov decision processes (improving for m > n4/3 an earlier bound of O(min(m 1.5, m·n2/3)). We also show that the same technique can be used to compute the maximal end-component decomposition of a graph in time O(n2), which is an improvement over earlier bounds for m > n4/3. Finally, we show how to maintain the winning set for Büchi objectives in alternating games under a sequence of edge insertions or a sequence of edge deletions in O(n) amortized time per operation. This is the first dynamic algorithm for this problem. Copyright © SIAM.

关键词： Markov processes

来源：评论

学校读者我要写书评

暂无评论

Bayesian network classifiers with reduced precision parameters

Bayesian network classifiers with reduced precision paramete...

引用

2012 European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML-PKDD 2012

作者： Tschiatschek, Sebastian Reinprecht, Peter Mücke, Manfred Pernkopf, Franz Signal Processing and Speech Communication Laboratory Graz University of Technology Graz Austria University of Vienna Research Group Theory and Applications of Algorithms Vienna Austria Sustainable Computing Research Austria

ISBN: (纸本)9783642334597

Bayesian network classifiers (BNCs) are probabilistic classifiers showing good performance in many applications. They consist of a directed acyclic graph and a set of conditional probabilities associated with the nodes of the graph. These conditional probabilities are also referred to as parameters of the BNCs. According to common belief, these classifiers are insensitive to deviations of the conditional probabilities under certain conditions. The first condition is that these probabilities are not too extreme, i.e. not too close to 0 or 1. The second is that the posterior over the classes is significantly different. In this paper, we investigate the effect of precision reduction of the parameters on the classification performance of BNCs. The probabilities are either determined generatively or discriminatively. Discriminative probabilities are typically more extreme. However, our results indicate that BNCs with discriminatively optimized parameters are almost as robust to precision reduction as BNCs with generatively optimized parameters. Furthermore, even large precision reduction does not decrease classification performance significantly. Our results allow the implementation of BNCs with less computational complexity. This supports application in embedded systems using floating-point numbers with small bit-width. Reduced bit-widths further enable to represent BNCs in the integer domain while maintaining the classification performance. © 2012 Springer-Verlag.

关键词： Probability

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：