direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

ALEPH: Algorithm Engineering for NP-hard Problems: Parameterized Algorithms versus Established Techniques

Funded by Deutsche Forschungsgemeinschaft (Project ALEPH, HU 2139/1)

project term: March 2013 - February 2016

Synopsis:

Many combinatorial problems from diverse application areas such as biology, operations research, or data mining, are NP-hard. In practice, mainly heuristics or mathematical programming (ILPs) are employed for such problems; however, these typically lack guarantees on solution quality or guarantees on running time. Parameterized algorithms are a recent approach that tries to solve problems from practice optimally in provably bounded time. Although there is much progress in the theory and the field has the explicit claim of applicability, there are few works on implementation and experiments with real-world data that lead to practically deployable software. In this project, first based on parameterized algorithmics new methods for solving NP-hard problems will be developed; these will then be implemented and compared to conventional technique approaches, in order to reach general recommendations. Further, parameterized techniques will be used to improve heuristics and ILP approaches. In this way, it will be examined how far parameterized algorithmics can hold up to the claim of delivering practically relevant solution methods. For this, also general principles and instructions will be developed that show how to attack a hard problem with the methods of parameterized algorithmics.

Head: Falk Hüffner

DAMM: Data Reduction in Parameterized Algorithmics - New Models and Methods

Funded by Deutsche Forschungsgemeinschaft (Project DAMM, NI 369/13) started in December 2012.

Synopsis:

Preprocessing by means of data reduction rules is a common approach for the algorithmic treatment of combinatorially difficult and compute-intensive problems. Parameterized Algorithmics formalizes the concept of preprocessing in terms of problem kernels. So far, research mainly focussed on the size of the problem kernel and lacked a broader analysis of preprocessing. Thus, the goal of DAMM is to investigate different aspects of preprocessing taking into consideration other interesting properties of problem kernels, such as the running time for example. We also aim at developing kernelizations with respect to "non-standard" and "multivariate" parameterizations which could be of practical interest. Finally, we will consider different kernelization models that generalize the concept of problem kernels, such as Turing kernels, analyzing their relations and possible applications.

People: Till Fluschnik

Head: Rolf Niedermeier

DAPA: Data Driven Parameterized Algorithmics for Graph Modification Problems

Funded by Deutsche Forschungsgemeinschaft (Project DAPA, NI 369/12) started in January 2012.

Synopsis:

Problems from many different fields like biology, operations research and image processing can be modeled as graph modification problems in a simple and elegant fashion. The task is then to modify the structure of a given graph according to particular conditions. Allowed modifications are often as simple as adding edges or deleting vertices or edges. Unfortunately, most graph modification problems are NP-hard, that is, they presumably admit no efficient algorithms for finding the minimum number of modifications needed. However, there is hope for relevant and efficiently solvable special cases because of the following. First, there is often only a small number of modifications needed in practice. Second, the input graphs often obey structures that are specific to the application. Both these observations can be used to create "problem parameterizations" which can be exploited in the development of efficient parameterized algorithms. In this project, finding such parameterizations will be data driven, that is, promising parameterizations will be extracted from "real world" data. We focus on applications in the context of "data clustering" and "planning". Aside from theoretical analyses we will also provide implementations and empirical evaluation.

Head: Rolf Niedermeier

DARE: Data Reduction and Problem Kernels

Funded by Deutsche Forschungsgemeinschaft (Project DARE, NI 369/11)

project term: March 2010 - January 2014

Synopsis:

Preprocessing by means of data reduction rules is a common approach for the algorithmic treatment of combinatorially difficult and compute-intensive problems. Typically, the data reduction approaches used so far have an ad hoc character and are not systematically developed. Theory construction has not taken place for this universally applicable method so far. With the concept of the problem kernels originating from parameterized complexity, it is now for the first time possible to undertake a systematic, theoretically supported investigation on the effectiveness of data reduction techniques. In addition, these theoretical investigations can—as shown in first case studies—very effectively guide the search for new, better data reductions. With algorithm engineering, practical tools can be developed, and the actual capability of data reduction rules in most diverse applications can be examined. Eventually, this opens up new application potential for this basic algorithmic technology.

People: Mathias Weller, Vincent Froese

Head: Rolf Niedermeier

PAWS: Parameterized Algorithmics for Voting Systems

Funded by Deutsche Forschungsgemeinschaft (Project PAWS, NI 369/10)

project term: May 2009 - February 2017

Synopsis:

Voting systems play a central role in modern society. Voting scenarios arise whenever the preferences of different parties have to be aggregated to form a joint decision. This is what happens in political elections, group decisions, web site rankings, or multiagent systems. There is a great variety of voting protocols that lead to a rich area of research questions. Questions arising in this area concern the efficient determination of a winner as well as manipulation, control, and lobbying. Many of these problems turn out to be NP-hard. The main goal of this project is the design of parameterized algorithms to efficiently analyze and handle voting systems.

People: Robert Bredereck

Head: Rolf Niedermeier

AREG: Algorithms for Generating Quasi-Regular Structures in Graphs

Funded by Deutsche Forschungsgemeinschaft (Project AREG, NI 369/9)

project term: February 2008 - December 2013

Synopsis:

Algorithms to find quasi-regular structures in graphs make up a broad field in graph algorithmics. A simple special case is the well-known Vertex Cover problem. Recently, new problems in this context with interesting applications were introduced, and new techniques were developed. Examples of such techniques are, e.g, the interative compression technique or the characterization via forbidden subgraphs. However, the studies of the problems and the techniques were quite specific and isolated from each other up to now. In this project, these problems and techniques are studied in a more general context, using all relevant algorithmic methods for NP-hard problems (including experiments).

People: René van Bevern and Ondřej Suchý

Head: Rolf Niedermeier

PABI: Parameterized Algorithmics for Bioinformatics

Funded by Deutsche Forschungsgemeinschaft (Project PABI, NI 369/7)

project term: October 2007 - February 2014

Synopsis:

The project "Parameterized algorithmics for bioinformatics (PABI)" heads at exploring and understanding the reasons for computational intractability (NP-hardness) of a large number of problems in algorithmic bioinformatics. As it turned out in recent years, the hardness of these problems can often be attributed to problem-specific parameters. In particular, if these problem parameters are small - and if the seemingly unavoidable combinatorial explosion inherent to the NP-hard problems can be confined to these parameters - then the concept of fixed-parameter tractability may offer an opportunity for efficient (and exact) algorithms despite NP-hardness.

People: Falk Hüffner and Manuel Sorge

Head: Rolf Niedermeier

Zusatzinformationen / Extras