- Stable sets and special graph classes
- Combinatorial online-planning
- Evolution and phase transitions
- Randomness in the design and analysis of discrete algorithms
- Geometry and combinatorics of 0/1-Polytopes
- Enumeration and random generation
Project 1: Stable sets and special graph classes
Stable sets in Graphs form one of the most important model structures in discrete optimization. In many applications the structure can be detected, explicitly or implicitly. The stable set problem is in general NP-hard, also from a computational point of view. For several graph classes it has been shown that the problem can be solved in polynomial time. In particular, the class of perfect graphs is of interest. The properties of perfect graphs form an interface between graph theory, polyhedral theory, communication theory and integer programming and constitute connections between these areas:
The relation between perfect graphs and information theory is probably deeper than well-known (Simonyi, 2001).
Perfect graphs can be characterized by means of graph entropy; the so-called degree of imperfection can be expressed by the graph entropy, and the graph entropy itself can be seen as entropy of the stable set polytope. This shows the close relationship between polyhedral-theoretical and information-theoretical characterisations of perfect graphs. The emphasis of the project is on the investigation of relaxations of these concepts on upper classes of perfect graphs.
Project 2: Combinatorial online-planning
In general, traditional optimization techniques assume complete knowledge of all data of a problem instance. However, there are many cases in practice where decisions have to be made before complete information about the data is available. This observation has motivated the research on online optimization. In online optimization the input is modeled as a (finite) request sequence, which must be served and which is revealed step by step to an online algorithm. After receiving a request, the online algorithm needs to compute a new (partial) solution, without knowledge about future requests.
Many real-world applications have an online nature. In this project, we investigate the basis for the design and analysis of online algorithms. The goal is to overcome the over-pessimistic view of the standard yardstick for online algorithms, the competitive analysis, and to find more meaningful performance measures of online algorithms. Hereto, three areas are at the center of our interests:
- analysis of randomized algorithms (randomness helps designing algorithms)
- analysis of algorithms on random input (randomness helps analyzing the "normal" behavior of algorithms)
- analysis of algorithms on restricted input instances.
Three elementary online-problems will function as the play ground for the design and analysis of online algorithms: the bin-coloring problem, Dial-a-Ride problems, and path-coloring problems in graphs.
Project 3: Evolution and phase transitions
Typically, a mathematical theorem states that all elements of some specified class possess a certain property. In contrast, the basic approach of this project is provided by Theme 1: (Characterization of random objects), i.e., one seeks for structural properties which hold with high probability for a randomly chosen element of the class.
In many cases, the probabilistic analysis of an algorithm (cf. Theme 3) depends heavily on the characterizations considered under Theme 1. Such an analysis, which measures the performance of an algorithm on a randomly (according to some given probability distribution) selected instance, is based upon the properties of a typical element in the solution space, and often a comprehensive picture of these structural properties arises only when the evolution of the underlying class is resolved.
An essential part of this project is concerned with examining the evolution of Gn,p, i.e., one would like to know how typical properties of Gn,p vary with increasing edge probability p. For many parameters the evolution behaviour is settled by now. For "complex" parameters, such as the list chromatic number or the Theta function, fundamental questions remain open. But new tools, like Talagrand's inequality, for example, have recently led to considerable advances.
Substantially less is known yet about the evolution of random graphs with constraints. Within this project, three different constraints will be considered:
- random graphs with forbidden subgraphs,
- random planar graphs, and
- so-called "small-world" networks.
An important aim when investigating such networks is the characterization (in the sense of Theme 2) of complex networks by suitable random models.
Project 4: Randomness in the design and analysis of discrete algorithms
For a number of familiar combinatorial optimization problems, such as graph colouring, the stable set problem in graphs, or the MAX-k-SAT problem, non-approximability results have been established. So, under certain complexity-theoretical assumptions, these problems do not admit polynomial-time algorithms that, for every instance, compute an optimal solution, or at least a good approximation. Therefore, already Karp asked for
- heuristics which on almost every instance produce a good solution to the optimization problem, and which have polynomial runtime for every instance, as well as for
- algorithms which, on every instance, guarantee an acceptable approximation quality, and which have expected polynomial runtime,
and thereby initiated the probabilistic analysis of algorithms. In the sense of Theme 3, this project is concerned with fundamental combinatorial problems like graph colouring, finding a largest stable set, or the satisfiability problem.
Alongside the probabilistic analysis, randomness shall also be studied as an algorithmic concept in this project. In the sense of Theme 4, the objective is then to develop improved algorithms by means of randomization.
Project 5: Geometry and combinatorics of 0/1-Polytopes
To a large extent, successes in combinatorial optimization in the last few decades have been based upon insights into the geometry of the polytopes corresponding to the various combinatorial problems. Such a polytope is, as a rule, the convex hull of the characteristic vectors of the considered combinatorial objects (e.g. subsets of edges in a graph, which are matchings). While the structure of numerous special classes of 0/1-polytopes (convex hulls of points with 0/1-coordinates) has been studied intensively, to date there is very litte known about the general class of 0/1-polytopes.
In this project we investigate various structural questions concerning 0/1-polytopes. Randomness plays two roles here: firstly, we investigate random 0/1-polytopes in order to obtain general structural knowledge about the overall class of 0/1-polytopes, secondly, much of the structural research is relevant for randomized, algorithmic problems on combinatorial objects, such as the random generation of a basis for a given matroid.
Project 6: Enumeration and random generation
For many finite classes of combinatorial objects - for example the spanning trees in a finite graph - the following four closely related problems occur in various contexts (in both theory and methodology):
- generate a random object/example,
- estimate the number of objects,
- determine the number of objects,
- generate a complete list of the objects.
In this project, we investigate a variety of such problems concerning the enumeration and the random generation within four areas of application.
Deutsch