Dr. Benjamin Doerr, MPI
Below I sketch some areas where I have some interesting topics for bachelor, master, diploma or PhD projects. Unless otherwise indicated, all areas allow projects on all levels. The descriptions naturally do not give every detail. For more precise information, please contact me. Also, note that the list is not necessarily complete. If you have other ideas that roughly qualify as discrete maths or theory of algorithms, please contact me.
Evolutionary algorithms gained significant attention in the last 20 or so years. Practitioners love then for being simple, cheaply to implement and robust algorithms that often yield surprisingly good results. Unfortunately, a theoretical understanding of this is still far away. However, in the last few years more and more results popped up that provide rigorous theoretical analyses of such algorithms. Similar statements are true for related randomized seach heuristics like ant colony optimization, particle swarm optimization or simulated annealing. Besides many tempting theoretical questions we do also have some very applied ones in this context.
A thesis in combinatorial game theory is a way to simultaneously (i) have good fun, (ii) do serious research and (iii) obtain results that have applications in computer science or engineering. Consult this page of a seminar I gave for slighly more information.
A hypergraph is nothing more than a ground set (`vertices’) together with some subsets thereof (`hyperedges’). The discrepancy problem for hypergraphs is to color the vertices with a fixed number of colors in such a way that (as good as possible) each hyperedge contains the same number of vertices in each color. Until very recently, this problem was only investigated for two colors [where it is already highly interesting]. Recent results of different authors indicated that many classical 2-color results have some kind of analogue for arbitrary numbers of colors. In [Doerr, The hereditary discrepancy is nearly independent of the number of colors, Proc. Amer. Math. Soc. 134 (2004)] some explanation of this phenomenon is given. Still there is some more work to be done in this problem field. If you're missing the application, you can also have a nice topic from data engineering or parallel and distributed systems. Say you have 2D geographical data such that each data block covers a small aligned square in the grid. You want to store these data blocks on several parallel disks, as this speeds up the data retrieval compared to a single disk (hopefully). To make this work, you should distribute the data wisely, namely in such a way that requests find their data evenly distributed on the disks.
The Propp machine is a deterministic process that moves chips on a graph. Each vertex is equipped with an arrow (rotor) pointing to one of its neighbors. Each time step, the rotor sends all chips lying on its vertex to neighboring vertices. It does so one chip after the other, sending a chip in the direction it is pointing and then updating its direction to another neighbor (following a given cyclic order). Hence the arrow mechanism ensures that the neighbors are served in a balanced manner.
One may therefore ask how well this Propp machine simulates a random walk. The answer is positive for many graphs. For the infinite path we have the following: No matter how many chips are used, no matter where they are placed on the graph initially (ok, please use only one of the bipartition classes), no matter how the arrows are initialized, no matter how long the machine is run, the number of chips on each vertex differs from the expected number of chips the random walk would have gotten on this vertex by at most 2.29. Here is some more information on the Propp machine.
Randomized rounding is a simple and powerful primitive in integer linear programming. However, so far it seems that many of its aspects are praised more in the theory community than in the applied sciences. For some particular facets, experimental results seem to be entirely missing.
The basic rounding problem related to integer linear programming (see also the previous topic) is, for given matrix A and vector x to find an integer vector y such that Ax is close to Ay (`small violation of the constraints’). Typically, y is obtained from x through clever rounding. A number of algorithms and results exist for this problem. In many applications, however, we need roundings that satisfy some constraints without violation. A very simple example is the problem to round a matrix to an integer one in such a way that the row and columns sums do not change (OK, let's assume they're integral first). Much less is known for such rounding problems with hard constraints, though people have begun working on this (e.g. Srinivasan [FOCS 2001], Gandhi et al. [FOCS 2002], Doerr [STACS 2005, STACS 2006]).
If you feel that you might be interested to work in one of the fields described above, or if you are interested in some area that seems to by close to my area of expertise, contact
Dr. Benjamin DoerrPS: This was not the recreation you were looking for? OK, try this one. n players, who may discuss their strategies beforehand, are being equipped each with a hat of color red or blue. Each one can see all hats except his own. Simultaneously and without further communication allowed they have to guess their own hat's color. Is there a strategy that guarantees that some players guess right?