Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

Monday Lecture and Colloquium

Monday, May 23, 2011

Technische Universität Berlin
Fakultät II, Institut für Mathematik
Str. des 17. Juni 136
10623 Berlin
room MA 041

Lecture - 14:15

Jon Lee - Watson Research Center (Yorktown)

Submodular-function maximization

Submodular-function maximization is a central unifying model in combinatorial optimization. Applications range from practical problems such as reconfiguring an environmental monitoring network, to more stylized problems such as the graph max-cut problem. I will describe some of the motivating applications, survey some different methodologies for maximizing a submodular function subject to side constraints, and describe computational results on environmental-monitoring problem instances for some of the more practical algorithms. Interestingly, while some of the algorithms are aimed at practical computation via an Operations Research / Mathematical Optimization approach, and others are driven by the Computer Science theory of approximation algorithms, there is significant common ground.

Colloquium - 16:00

Daniel Werner - FU Berlin

A Proof of the Oja Depth Conjecture in the Plane

For a set of n points in the plane, the Oja Depth of a point x is the sum of the areas of all triangles defined by x and two points from P, normalized by the area of convex hull of P. The Oja Depth of P is the minimum Oja Depth of any point in R^2. The Oja Depth Conjecture states that any set P of n points in the plane has depth at most (n^2)/9. This would be optimal as there are examples where it is not possible to do better. In this talk, we present a proof of this conjecture. In particular, we show that the center of mass of the convex hull has at most the desired depth. We also sketch an improvement for the higher dimensional case via a different, more combinatorial method. (Joint work with Nabil H. Mustafa and Hans Raj Tiwary)