Logo der Universität Wien

About us

Graph algorithms and their applications

Graphs are used to model relationships between items in a wide variety of applications. One such application is computer aided verification, where the system or program to be verified is modeled as a graph with the vertices representing the states of the system and the edges representing transitions between them. Properties of the resulting graph are then used to determine the correctness of the system or program. Thus graph algorithms lie at the heart of computer-aided verification systems.

Modern algorithmic techniques, such as dynamic graph algorithms and randomization, have been developed in recent years and have helped to speed up numerous problems from finding minimum cuts in networks to finding homeomorphic subtrees in evolutionary biology. However, current graph algorithms in computer aided verification do not use these techniques and our goal is to explore how they can be used to design faster algorithms for core algorithmic questions, such as liveness and parity specifications. In our joint research project with Krishnendu Chatterjee at IST Austria we designed more efficient algorithms for various fundamental problems in computer verification and we plan to extend this promising research to other graph algorithmic problems in verification in the future.

We are also working on efficient algorithms for other applications such as graph algorithmic problems arising in computational biology and internet advertisements.

 

Algorithmic game theory

The field of algorithmic game theory studies a wide variety of computational questions arising in game theory. They reach from complexity questions, such as the complexity of computing certain equilibria in games, to learning questions in repeated games, to assignment and pricing questions in specific markets. Motivated by problems in online advertisement systems we are currently studying the latter type of questions on a research project funded by the WWTF. In online advertising there are different types of web properties, e.g., search result pages, content pages, and publisher web sites, that allow different types of user targeting, varying between no and very detailed knowledge about the user. Additionally there are different kinds of payment schemes, for example, pay-per-click (e.g., costs are incurred every time the advertisement is clicked on), pay-per-impression (e.g., costs are incurred every time the advertisement is shown), or pay-per-day (e.g., a fixed amount is paid every day). The assignment question is which advertisement to show whenever a user visits a given page. The pricing question is how much the advertiser has to pay in his payment scheme. Of course, these questions are not limited to the web, they can be applied also to advertisements on mobile phones or other media. Furthermore, pricing questions are not limited to advertisements. For example, we are also studying how to price recommendations of products by email or in social networks or how to price an item if the valuation that a customer has for the item has externalities, e.g., depends on whether his friends have bought an recommended the item.

 

Reliable distributed aggregation algorithms

Unreliable distributed networks, such as sensor networks or peer-to peer networks, motivate the investigation of distributed algorithms with high resilience and fault tolerance at the algorithmic level. In these aspects, there is often a rather significant gap between existing algorithmic theory and computational practice. Most of the distributed algorithms considered in the literature provide only a very limited extent of flexibility and resilience against failures such as (silent) message loss, and link or node failures. Although it has been shown that convergence can be guaranteed even in the presence of failures, existing algorithms will in general not converge to the correct result, but to some perturbation of it.

Our current focus is on gossip- and consensus-based distributed aggregation algorithms (e.g., distributed summation or distributed averaging). We are working on a methodology for generically deriving reliable variants of linear iteration-based distributed aggregation algorithms which provably deliver correct results despite failures in the environment. Overhead for the increased robustness is only incurred if failures happen – in a failure-free environment, our new algorithms have the same behavior as the existing non-reliable algorithms.

Beyond robustness at the algorithmic level, we are also investigating distributed algorithms for wireless networks (broadcasting vs. point-to-point communication) or mobile nodes (dynamically changing network topologies), and latency aspects (runtime requirements, efficient implementations). Together with our research partners in the NFN SISE of the Austrian Science Fund FWF we are working on the application of these new algorithmic techniques in problems arising in signal processing and telecommunications.

 

High performance/distributed numerical linear algebra

The field of high performance algorithms for numerical linear algebra has always been strongly influenced by the rapid development of hardware architectures. Two concepts which are currently very influential for the development of new algorithmic approaches are multi/manycore architectures and hetereogeneous system architectures (typically CPUs combined with accelerators such as GPUs). Beyond that, new types of algorithmic challenges (in addition to numerical accuracy and high performance) arise on the road towards exascale computing. Important examples are parallel scalability to extremely large processor numbers, fault tolerance at the algorithmic level or reduced synchronization requirements.

In this context, we are currently working on new algorithmic approaches for structured (in particular, banded) eigenvalue problems, on distributed methods for matrix computations (on the basis of the distributed aggregation algorithms mentioned above), and on mixed precision approaches for eigenvalue problems. In the first topic, we developed new algorithms which have advantages over the state-of-the-art methods for small bandwidths and/or for clustered eigenvalues. In the second topic, we successfully designed fully distributed gossip-based and consensus-based orthogonalization methods and a fully distributed eigensolver.

 

Contact us
Faculty of Computer Science
University of Vienna

Währinger Straße 29
A-1090 Vienna