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

7th International Workshop on Internet and Network Economics, WINE 2011

作者： Vidali, Angelina Theory and Applications of Algorithms Research Group University of Vienna Austria

ISBN: (纸本)9783642255090

The already extended literature in Combinatorial Auctions, Public Projects and Scheduling demands a more systematic classification of the domains and a clear comparison of the results known. Connecting characterization results for different settings and providing a characterization proof using another characterization result as a black box without having to repeat a tediously similar proof is not only elegant and desirable, but also greatly enhances our intuition and provides a classification of different results and a unified and deeper understanding. We consider whether one can extend a characterization of a subdomain to a domain in a black-box manner. We show that this is possible for n-player stable mechanisms if the only truthful mechanisms for the subdomain are the affine maximizers. We further show that if the characterization of the subdomain involves a combination of affine maximizers and threshold mechanisms, the threshold mechanisms for the subdomain cannot be extended to truthful mechanisms for the union of the subdomain with a (very slight) affine transformation of it. We also show that for every truthful mechanism in a domain there exists a corresponding truthful mechanism for any affine transformation of the domain. We finally plug in as a black box to our theorems the characterization of additive 2-player combinatorial auctions that are decisive and allocate all items (which essentially is the domain for scheduling unrelated machines) and show that the 2-player truthful mechanisms of any domain, which is strictly a superdomain of it are only the affine maximizers. This gives a unique characterization proof of the decisive 2-player mechanisms for: Combinatorial Public Projects, Unrestricted domains, as well as for Submodular and Subadditive Combinatorial Auctions that allocate all items. © 2011 Springer-Verlag Berlin Heidelberg.

关键词： Scheduling

来源：评论

学校读者我要写书评

暂无评论

A fast solver for modeling the evolution of virus populations

A fast solver for modeling the evolution of virus population...

引用

2011 International Conference for High Performance Computing, Networking, Storage and Analysis, SC11

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

ISBN: (纸本)9781450307710

Solving Eigen's quasispecies model for the evolution of virus populations involves the computation of the dominant eigenvector of a matrix whose size N grows exponentially with the chain length of the virus to be modeled. Most biologically interesting chain lengths are so far well beyond the reach of existing algorithms and hardware. We show how to exploit the special properties of the problem under consideration and design a fast and accurate solver which reduces the complexity to Θ(N log2 N). Our solver is even faster than existing approximative strategies and contrary to those it can also be applied to more general formulations of the quasispecies model. Substantial further improvements and high parallelism can be achieved for special fitness landscapes in the evolution model. Beyond theoretical analysis, we evaluate the performance of our new solver experimentally on a GPU with an OpenCL implementation and illustrate that it achieves speedup factors of more than 107 over standard approaches. Copyright 2011 ACM.

关键词： Graphics processing unit

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Robust distributed orthogonalization based on randomized aggregation

Robust distributed orthogonalization based on randomized agg...

引用

2011 ACM Workshop on Scalable algorithms for Large-Scale Systems, ScalA'11, Co-located with SC'11

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

ISBN: (纸本)9781450311809

The construction of distributed algorithms for matrix computations built on top of distributed data aggregation algorithms with randomized communication schedules is investigated. For this purpose, a new aggregation algorithm for summing or averaging distributed values, the push-flow algorithm, is developed, which achieves superior resilience properties with respect to node failures compared to existing aggregation methods. On a hypercube topology it asymptotically requires the same number of iterations as the optimal all-to-all reduction operation and it scales well with the number of nodes. Orthogonalization is studied as a prototypical matrix computation task. A new fault tolerant distributed orthogonalization method (rdmGS), which can produce accurate results even in the presence of node failures, is built on top of distributed data aggregation algorithms. © 2011 ACM.

关键词： Matrix algebra

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Performance Evaluation of Computer and Communication Systems. Milestones and Future Challenges 1

引用

丛书名： Lecture Notes in Computer Science

1000年

作者： Karin Anna Hummel Helmut Hlavacs Wilfried Gansterer

ISBN: (数字)9783642255755

ISBN: (纸本)9783642255748

This Festschrift volume is published in honor of Günter Haring on the occasion of his emerital celebration and contains invited papers by key researchers in the field of performance evaluation presented at the workshop Performance Evaluation of Computer and Communication Systems - Milestones and Future Challenges, PERFORM 2010, held in Vienna, Austria, in October 2010. Günter Haring has dedicated most of his scientific professional life to performance evaluation and the design of distributed systems, contributing in particular to the field of workload characterization. In addition to his own contributions and leadership in international research projects, he is and has been an excellent mentor of young researchers demonstrated by their own brilliant scientific careers. The 20 thoroughly refereed papers range from visionary to in-depth research papers and are organized in the following topical sections: milestones and evolutions; trends: green ICT and virtual machines; modeling; mobility and mobile networks; communication and computer networks; and load balancing, analysis, and management.

关键词： Information Systems applications (incl. Internet) Computer Communication Networks Software Engineering Algorithm Analysis and Problem Complexity Artificial Intelligence Information Storage and Retrieval

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Abstract: Gossip-Based Distributed Matrix Computations

Abstract: Gossip-Based Distributed Matrix Computations

引用

High Performance Computing, Networking, Storage and Analysis (SCC), SC Companion:

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

We investigate randomized distributed algorithms for matrix computations over loosely coupled distributed systems, such as P2P networks or sensor networks. In this poster, we discuss orthogonalization methods and orthogonal iteration. These algorithms are very well understood in the sequential or in the classical parallel context, and they are important building blocks for many algorithms in numerical linear algebra.

关键词：

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：