Abgeschlossene Projekte

• Graduiertenkolleg: Algorithmische Synthese reaktiver und diskret kontinuierlicher Systeme (AlgoSyn)
  funded by the DFG (July 2006 - May 2015)
• UMIC - Ultra High-Speed Mobile Information and Communication
  funded by the DFG, Research Cluster in the Excellence Initiative (November 2006 - October 2014)
• Generalized Congestion Games: Analysis, Computation, and Evolution
  funded by the German-Israeli Foundation for Scientific Research and Development (GIF) (January 1, 2007 - December 31, 2010)
• Management variabler Datenströme in Netzwerken
  funded by the DFG, Schwerpunkt 1126 (since July 2001)
• DELIS - Dynamically Evolving Large Scale Information Systems
  funded by the European Union, Integrated Project (since Jan 2004)
• Graphs and Algorithms in Communication Networks
  funded by the European Science Foundation, Cost Action 293 (since Jan 2005)
• Flexible Online-Algorithmen
  funded by the DFG (since Jan 2003)
• Probabilistische Analyse diskreter Optimierungsprobleme
  funded by the DFG (since Oct 2005)

• Algorithmic synthesis of reactive and discrete-continuous systems
  funded by the DFG (July 2006 - May 2015)
  
  AlgoSyn is an interdisciplinary research project at the RWTH Aachen University led by a group of ten professors representing five different disciplines. Integrating approaches from computer and engineering sciences, the project aims at developing methods for the automatised design of soft- and hardware.
  
  While methods of software validation and verification are by now well established, based on adequate formal models and tested in practical applications, the approach of automatic synthesis of software (and hardware) is as yet only developed in quite rudimentary form. On the other hand, in theoretical computer science as well as in engineering disciplines a rapidly increasing stock of techniques for the development of algorithmic synthesis procedures is emerging, triggered by the demand to decrease development costs by invoking algorithmics in formal modelling frameworks. However, the approach of program synthesis is only applicable in restricted scenarios, in particular in reactive (multi-agent) systems with low data complexity and in control systems. Central issues in the area are the establishment of system models which allow an algorithmic solution of the synthesis problem, the combination of discrete and continuous pararameters in hybrid systems (as this is also familiar from verification), and the exploration of the potential of applications. The aim of the Graduate School is to unify the expertise from Computer science, mathematics, and four engineering disciplines (processor architectures, automatic control, process control engineering, train traffic systems) and to push forward the desired integration of methods. The research will be carried out in four subject areas: Algorithmics for agent-based probabilistic and hybrid systems, formal methods of reactive systems and game-theoretic methods, software development and modelling languages, and finally applications and demonstrators.
• UMIC - Ultra High-Speed Mobile Information and Communication
  funded by the DFG, Research Cluster in the Excellence Initiative (November 2006 - October 2014)
  
  The initial goal of the UMIC cluster was to enable future Ultra High-Speed Mobile Information and Communication, with the main vision of broadband wireless internet access at reasonable access costs triggering the next wave of economic and innovation growth. Today it is indeed the low cost access, predominantly in the form of flat data rates, which drives the exponentially increasing mobile Internet access. This has led to a strong cost pressure on operators and equipment providers. Researching technologies that address these problems has thus been the right approach. Over time mobile internet access grew rapidly. UMIC reacted to this with a shift in the focus to Universal Mobile Access to Information and Communication, thus putting more emphasis on the user perspective with technologies supporting universal mobile access.
  
  A major differentiator of the research centre to competitors and the usual chair based systems in faculties is its ability to closely collaborate, addressing particular problem domains on a broader scale. In UMIC three interdisciplinary flagship projects emerged over the course of the collaboration: LocalizeMe, addressing application topics, Cognitive Radios and Networks, addressing flexible and efficient use of the wireless communication resources, and Nucleus, addressing platforms and design methodology for flexible (mobile) terminals. Research in the UMIC centre produced substantial scientific results documented by, e.g. more than 1,000 peer-reviewed journal and conference papers, by extensive technology transfer to industry partners and via start-up companies and by one Leibniz Prize and three ERC Grants received during the UMIC funding period.
  
  Further, the UMIC research cluster has led to cultural and structural changes in the involved departments of RWTH Aachen University. Most notably, it has successfully introduced a structured career path for junior researchers based on Junior Professor positions (assistant professorship). Out of 6 established junior professorships 3 have got tenure in Aachen, 2 in other international top universities, and one more is still in the tenure track. This shows the high quality of the candidates the UMIC was able to attract. UMIC gender equality promotion activities contributed significantly to a development where both Computer Science and Electrical Engineering departments increased the percentage of female researchers in post study career stages (i.e. Doctoral degrees and Professors) to a balance with the percentage of female students. Last but not least UMIC has been intellectual home for 176 doctoral researcher of which 97 have already successfully defended their doctoral thesis work.
  
  The UMIC research centre building, the new research groups and the five labs with state-of-the-art equipment teams established through UMIC funding are the basis of sustained UMIC research. Moreover, UMIC research is a key component of the strategy of the Information and Communication Technology (ICT) profile area of RWTH Aachen University.
• Generalized Congestion Games: Analysis, Computation, and Evolution
  funded by the German-Israeli Foundation for Scientific Research and Development (GIF) (January 1, 2007 - December 31, 2010)
  
  The project proposes to bring together two disciplines - computer science and game theory - and by doing so to address some fundamental problems of computing in the Internet era. Combining our expertise we propose to handle several complementary issues in non-cooperative multi-agent systems. Since we can show that congestion and network games with player-specific payoff functions give us the set of all strategic games, while congestion games with player-symmetric payoff functions are the most popular type of games discussed in the computer science literature, the study of generalized congestion games is a most effective way to bridge the gap between computer science and game theory.
  
  When referring to generalized congestion games we refer both to congestion games where agents may have different payoffs functions, as well as to congestion games with uncertainty (e.g. about the number of participants or other agents' costs). The nice graph-theoretic representation of general strategic games as player-specific congestion games enables to tackle the fundamental problem of existence of solution concepts (e.g. pure strategy equilibrium or strong equilibrium) as a function of the graph structure, as well as determine the complexity of computation and the speed of convergence to solutions as a function of the graph structure. In order to deal with congestion games with incomplete information, our aim is to tackle reasoning about uncertainty in multi-agent systems when exact probabilistic information is not available. For doing so, new equilibrium concepts are to be defined and applied to congestion settings.
  
  This is a joint project with Dov Monderer and Moshe Tennenholtz from the Technion.
• Management variabler Datenströme in Netzwerken
  funded by the DFG, Schwerpunkt 1126 (since July 2001)
  
  This project deals with dynamic routing algorithms in large networks like the Internet. The goal is to improve our understanding of communication patterns as well as to design algorithms routing the data in such a way that the communication load is as evenly distributed over the available resources as possible. This gives us the opportunity to avoid congestion on the one hand and to guarantee a fair treatment of all participating users on the other hand. In particular, we aim at the design of algorithms for allocating streams of data on web servers as well as for performing intra-domain routing in networks. The resulting research problems will be tackled theoretically, practically, and experimentally. The project is part of the DFG research program "Algorithmik großer und komplexer Netzwerke". We closely cooperate with the networking group of the TU München headed by Anja Feldmann. Our particular focus in this cooperation is mainly on the theoretical part.
• DELIS - Dynamically Evolving Large Scale Information Systems
  funded by the European Union, Integrated Project (since Jan 2004)
  
  Most of the existing and foreseen complex networks are built, operated and used by a multitude of diverse economic interests. A prime example is the Internet, perhaps the most complex computational artifact of our times. The (possibly) selfish nature of the participating entities calls for a deeper understanding of the network dynamics in order to efficiently achieve their cooperation, by possibly considering bounded rationality aspects. In the past few years, there has been a flourishing amount of work in the border of Computer Science, Economics, Game Theory and Biology that has started to address the above issues. For example, (a) selfish network routing (and flows) were addressed in a number of recent research papers, (b) mechanism design for algorithmic cooperation of selfish users was proposed by many authors, (c) evolutionary economics addresses the dynamics of self-organization in large networks, and (d) the issues of bounded rationality of machines versus their ability for game playing were examined by several research groups, among them the Nobel-prized Economists work of 2001 and 2002.
  
  Activities within the project can be grouped into two main classes:
  
  Basic Research: basic research to understand the dynamics of the network and the effect of concepts like self-organization, selfishness and bounded rationalism as well as the structure of equilibria (and the form of dynamics) in such systems.
  
  Efficient Algorithms: design of mechanisms and algorithms that efficiently achieve the cooperation between the involved selfish entities, possibly applying results from evolutionary models.
• Graphs and Algorithms in Communication Networks
  funded by the European Science Foundation, Cost Action 293 (since Jan 2005)
  
  The main objective of this Action is to create a discussion space between applied communities and theorists in the context of communication networks in which models and assumptions can be reviewed and formalized into the appropriate language.
  Inside the context of communication networks, the Action focusses on, but is not restricted to the following specific fields:
  
  
  • QoS networks: Quality of Service (QoS) refers to a broad collection of networking technologies and techniques. The goal of QoS is to provide guarantees on traffic transmission. Elements of network performance within the scope of QoS include availability (uptime), bandwidth (throughput), latency (delay), delay jitter, and error rate.
  • Optimization in optical networks: Optical networks using light paths in optical fibers as communication media induce a number of problems that cannot be directly resolved by using standard solutions from electronic networks, but require new approaches and techniques, instead. These problems include routing techniques, wavelength assignment on switches and cross connects, signalling, topologies design, and path recovery (backup) for protection and restoration.
  • Optimization in wireless networks: Wireless networks were traditionally related with voice and telephony. Nowadays, packet networks are also supported in mobile, such as in GPRS and UMTS technologies. Trends on wireless networks include QoS for multimedia transmission and backup paths. Therefore, problems for static networks are moving to wireless, such as delay minimization, traffic engineering, frequency assignment and localization. But there are several additional challenges for wireless networks, one is for instance the coordination of the single uncontrolled agents participation in the network.
• Flexible Online-Algorithmen
  funded by the DFG, Emmy-Noether-Programm (since Jan 2003)
  
  Online algorithms studied in theory are characterized by the fact that they do not have knowledge about the whole input sequence of jobs in advance. Instead, the input sequence is generated job by job, and a new job is not issued until the previous one is handled by the online algorithm. In real applications, jobs can usually be delayed for a short amount of time, and hence the input sequence of jobs can be rearranged in a limited fashion to optimize the performance. This flexible online scenario occurs in many applications in computer science and economics, e.g., in computer graphics: A rendering system displays a sequence of primitives. The number of state changes of such a system are a significant factor for the performance. State changes occur when two consecutively rendered primitives differ in their attribute values, e.g., in their texture or shader program. With the help of a reordering buffer in which primitives can be buffered the sequence of primitives can be reordered online in such a way that the number of the state changes is reduced.
• Probabilistische Analyse diskreter Optimierungsprobleme
  funded by the DFG (since Oct 2005)
  
  Many algorithmic problems are hard from a worst-case point of view but can be solved quite well on typical inputs by heuristic approaches. Hence, worst-case complexity does not seem to be an appropriate measure for the complexity of these problems. This research project deals with the probabilistic analysis of such problems and heuristics in order to narrow the gap between the observations made in practice and the theoretical understanding of these problems.
  
  For many problems, average-case analyses do not provide much insight either since inputs which occur in practice usually possess certain properties and a certain structure which cannot be reflected by an average-case analysis alone as it is not clear how to choose the underlying probability distribution over the set of possible inputs. In this project, we turn our attention to more general probabilistic input models like, e.g., the model of smoothed analysis. The semi-random input model used in a smoothed analysis consists of two stages. First an adversary chooses an input, then this input is randomly perturbed in the second step. In particular, the adversary can specify a worst-case input with certain properties which is only slightly perturbed in the second stage.
  
  The focus of our research are problems which can be expressed in the form of integer linear programs. In our previous analyses we have characterized the class of integer optimization problems with polynomial smoothed complexity. The algorithms with polynomial smoothed complexity we designed, however, are clearly outperformed by common heuristics used in practice, like, e.g., Branch and Bound and Branch and Cut approaches. One of the main goals of this research project is the probabilistic analysis of these heuristics in order to understand why they perform so extraordinary well in practice. Our approach consists of two steps: First structural parameters like, e.g., the number of Pareto optimal solutions or the integrality gap, are analyzed. Then the running time of the heuristics is analyzed in terms of these parameters.